Cod sursa(job #3323348)

Utilizator boboc132Boboc Teodor boboc132 Data 18 noiembrie 2025 09:16:49
Problema Oite Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <vector>
using namespace std;

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

const int C_MAX=1025;
int oite;
long long lana,LAN[C_MAX];
int rez;
unordered_map<long long,int>grupa1;
//ideea 1
// caut a+b+c+d=lana brut are venii 4 foruri nestate
//ideea 2
// fac asa a+b=Lana-(c+d)  a+b e o perece dau cu 2 foruri nestate
// si dupa daut perechea adica prima pereche(a+b)care e egala cu Lana-(c+d);
//ideea 3
//stochez prima pereche (a+b) intreun unordered_map care ar tine suma lor adica grupa1[a+b][cheia] cheia i este nurmau de perechi care imi dau suma a+b
//problema
//sunt sanse sa iau a+b=Lan-(a+c)
//intrebarea acum:
//cum imi dau seama ca am duplicate?
//respuns:
//fortez scrierea (INDICII TREBUIE SA FIE DIFERITI ADICA SA N AM ACEEASI OITA) DOUA DIFERITE POT AVEA ACEEASI LANA
//i<j<k<l

//I<J   <K<L ???
//I+J+K+L=LANA 
//I+J=LANA-(K+L)
int main(){
    in>>oite>>lana;
    for(int i=1;i<=oite;i++)
        in>>LAN[i];
    /*
    for(int k=1;k<oite;k++){
        for(int l=k+1;l<=oite;l++){
            int Snecesare=lana-(LAN[k]+LAN[l]);
            rez+=grupa1[Snecesare];
        }
    }
    for(int i=1;i<=oite;i++){
        for(int j=i+1;j<oite;j++){
            long long sum=LAN[i]+LAN[j];
            grupa1[sum]+=1;
        }
    }
    dupa care e,prima data caut si dupa adaug ca sa nu am duplicate
    da in codu asta duma e sau...nush daca merge
    */
    for(int j=1;j<oite;j++){
        for(int i=j+1;i<=oite;i++){
            long long Snecesar=lana-(LAN[j]+LAN[i]);
            rez+=grupa1[Snecesar];
        }
        for(int k=1;k<j;k++){
            int sum=LAN[j]+LAN[k];
            grupa1[sum]++;
        }   
    }
    out<<rez;
}