Cod sursa(job #1761407)

Utilizator andrei_diaconu11Andrei C. Diaconu andrei_diaconu11 Data 22 septembrie 2016 10:02:52
Problema Oite Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <iostream>
#include <deque>
#include <vector>
#include <set>
#define NMAX 200005
#define MOD 100013

using namespace std;

typedef pair<int, int> pii;

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

int v[1024];
vector<pii> Hash[MOD];

int find_hash(int x) {
    int lista=x%MOD;

    for(auto it:Hash[lista]) if(it.first == x)  return it.second;

    return 0;
}

void insert_hash(int x) {
    int lista=x%MOD;

    if(!find_hash(x)) Hash[lista].push_back({x,1});
    else {
        for(auto &it:Hash[lista]) {
            if(it.first == x) {
                ++it.second;
                return;
            }
        }
    }
}

int main(){
    int n,i,j,s;
    long long res=0;

    fin>>n>>s;
    for(i=0;i<n;++i) fin>>v[i];

    for(i=0;i<n;++i) {
        for(j=i+1;j<n;++j)
            if(v[i]+v[j]<=s)
                res+=find_hash(s-v[i]-v[j]);

        for(j=0;j<i;++j)
            insert_hash(v[i]+v[j]);
    }

    fout<<res;

    return 0;
}