Cod sursa(job #1389845)

Utilizator andreey_047Andrei Maxim andreey_047 Data 16 martie 2015 18:13:12
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <iostream>
#include <cstdio>
#include <bitset>
#include <algorithm>
#define nmax 100005
using namespace std;
int n,x,len,m,best;
long long sum;
bitset<nmax>v;
struct Coord{
    int d,b;
};
Coord a[nmax];
inline  bool cmp(const Coord A,const Coord B){
    if(A.d == B.d) return A.b > B.b;
 return A.d > B.d;
}
int main(){
    int i,j,ok,poz;
    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);
    scanf("%d%d%d",&n,&x,&len);
    for(i=1;i<=n;i++){
        scanf("%d%d",&a[i].d,&a[i].b);
    }
    sort(a+1,a+n+1,cmp);
        for(i=1;i<=n;i++){
            best=ok=0;
      if(a[i].d + len*m <= x){
            if(a[i].d + len*m + len <= x){
                j=i;
                 while(a[j].d+len*m+len <= x && j<=n){
                    if(!v[j]&&a[j].b > best){poz=j;best=a[j].b;}
                    j++;
                     }
                 v[poz]=1;
                 sum+=best;i--;
                m++;
                    continue;}
        j=i;
         while(a[j].d+len*m <= x && a[j].d+len*m+len > x&&j<=n){
                 if(!v[j])
                best=max(best,a[j].b);
                    j++;
         }

        i=j-1;
        if(best){
        m++;
        sum+=best;
      }
    }}
      cout<<sum<<'\n';
    return 0;
}