Cod sursa(job #1938967)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 25 martie 2017 12:59:45
Problema Oite Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <fstream>
#include <vector>
#define DIM 1018
using namespace std;
long long n,S,i,v[1027],x,y,j,k,sol,nr;
vector < long long > H[DIM];

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 (v[1]+v[2]);
    //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]);
            y = H[x%DIM].size ();
            nr = 0;
            for (k=0;k<y;k++){
                if (H[x%DIM][k] == x){
                    nr++;
                    //break;
                }
            }
            if (nr != 0)
                sol += nr;
        }
        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 ();
            H[x%DIM].push_back (x);
        }
    }
    fout<<sol;

    return 0;
}