Cod sursa(job #1076829)

Utilizator andreiiiiPopa Andrei andreiiii Data 10 ianuarie 2014 17:05:18
Problema Peste Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <algorithm>
#include <cstdio>
#include <queue>
#define PII pair<int, int>
#define x first
#define y second

using namespace std;

const int N=50005, M=1001;

int main()
{
    freopen("peste.in", "r", stdin);
    freopen("peste.out", "w", stdout);
    int t=0, n=0, k=0, i, j;
    long long s=0;
    long long b[N], c[1001];
    PII a[N];
    char cit[50], *p;
    priority_queue <int, vector<int>, greater<int>> h;
    fgets(cit, 50, stdin);
    for(p=cit;*p>='0'&&*p<='9';p++) n=10*n+*p-'0'; p++;
    for(;*p>='0'&&*p<='9';p++) k=10*k+*p-'0'; p++;
    for(;*p>='0'&&*p<='9';p++) t=10*t+*p-'0';
    for(i=1;i<=n;i++)
    {
        fgets(cit, 50, stdin);
        for(p=cit;*p>='0'&&*p<='9';p++) a[i].y=10*a[i].y+*p-'0'; p++;
        for(;*p>='0'&&*p<='9';p++) a[i].x=10*a[i].x+*p-'0';
    }
    sort(a+1, a+n+1);
    b[0]=c[0]=0;
    for(i=1;i<=n;i++)
    {
        s+=a[i].y;
        h.push(a[i].y);
        if(i>k)
        {
            s-=h.top();
            h.pop();
        }
        c[a[i].x]=s;
    }
    for(i=1;i<M;i++) if(c[i]<c[i-1]) c[i]=c[i-1];
    for(i=1;i<=t;i++)
    {
        b[i]=c[i];
        for(j=1;i-j>0&&j<M;j++)
        {
            if(b[i]<b[i-j]+c[j]) b[i]=b[i-j]+c[j];
        }
        if(b[i]<b[i-1]) b[i]=b[i-1];
    }
    printf("%lld", b[t]);
}