Cod sursa(job #2953905)

Utilizator RamanujanNeacsu Mihnea Ramanujan Data 12 decembrie 2022 16:50:29
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>
#include<algorithm>
#define MAXN 100000
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
int sefi[MAXN*6];///timpii in care ies oile
pair<int, int> a[MAXN];
bool cmp(pair<int, int> x, pair<int, int> y){
    return x.first>y.first;
}
int find(int x){
    if(sefi[x]==x)
        return x;
    else
        return sefi[x]=find(sefi[x]);///compresia caii
}
void unify(int x, int y){
    int sefX=find(x), sefY=find(y);
    sefi[sefY]=sefX;
}
int main()
{
    int n, dist, delta; fin>>n>>dist>>delta;
    int maxTime=0;
    for(int i=0; i<n; i++){
        fin>>a[i].second>>a[i].first;
        a[i].second=((dist-a[i].second)/delta)+1;///timpul in care oaia iese din interval
        maxTime=max(maxTime, a[i].second);
    }
    for(int i=0; i<maxTime+1; i++)
        sefi[i]=i;
    sort(a, a+n, cmp);///voi vrea sa iau cele mai lanoase oi, daca pot
    long long checo=0;
    for(int i=0; i<n; i++){
        int x=a[i].second;
        int place=find(x);
        if(x>0){
          if(place>0&&a[i].second>0){///daca se mai poate lua oaie
             checo+=(long long)a[i].first;
             unify(place-1, place);///nota: unify il leaga pe primul la al doilea, asa ca trb in ord asta
          }
        }
    }
    fout<<checo;
    return 0;
}