Cod sursa(job #1939004)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 25 martie 2017 13:15:18
Problema Oite Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>
#include <vector>
#define DIM 500010
using namespace std;
int n,S,i,v[1027],x,y,j,k,nr,ok;
long long sol;
vector < pair<int,int> > H[DIM+3];

ifstream fin ("oite.in");
ofstream fout ("oite.out");

int main (){

    fin>>n>>S;
    for (i=1;i<=n;i++)
        fin>>v[i];
    // pun in multime pe v[1] + v[2]
    H[(v[1]+v[2])%DIM].push_back (make_pair(v[1]+v[2],1));
    //H2[(v[1]+v[2])%DIM][0].push_back (1); // aparitiile
    for (i=3;i<n;i++){
        for (j=i+1;j<=n;j++){
            // verificam daca apare s-(v[i] + v[j]) in multime
            x = S-(v[i] + v[j]);
            if (x < 0)
                x += DIM;
            y = H[x%DIM].size ();
            nr = 0;
            for (k=0;k<y;k++){
                if (H[x%DIM][k].first == x){
                    sol += H[x%DIM][k].second;
                    break;
                }
            }

        }
        for (j=i-1;j>=1;j--){
            // introducem pe v[i] + v[j] in multime
            x = v[i] + v[j];
            y = H[x%DIM].size ();
            ok = 0;
            for (k=0;k<y;k++){
                if (H[x][k].first == x){
                    H[x][k].second ++;
                    ok = 1;
                    break;
                }
            }
            if (ok == 0)
                H[x%DIM].push_back (make_pair(x,1));
        }
    }
    fout<<sol;

    return 0;
}