Cod sursa(job #3194690)

Utilizator AndreiBOTOBotocan Andrei AndreiBOTO Data 18 ianuarie 2024 22:13:52
Problema Peste Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>

#pragma optimize GCC ("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

///#include <tryhardmode>
///#include <GODMODE::ON>

using namespace std;

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

const int NMAX=5e4+5;
#define int long long

int dp_time[NMAX];
int dp_tank[NMAX];

struct elem {
    int shark_tank;
    int time;
}v[NMAX];

bool cmp(elem a,elem b)
{
    if(a.time==b.time)
        return a.shark_tank>b.shark_tank;
    return a.time<b.time;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

    int n,i,j,t,k,curr=0;
    priority_queue<int,vector<int>,greater<int>>pq;
    fin>>n>>k>>t;
    t=min(t,1000LL);
    for(i=1;i<=n;i++)
        fin>>v[i].shark_tank>>v[i].time;
    sort(v+1,v+n+1,cmp);
    for(i=1;i<=n;i++)
    {
        curr+=v[i].shark_tank;
        pq.push(v[i].shark_tank);
        if(pq.size()>k)
        {
            curr-=pq.top();
            pq.pop();
        }
        dp_tank[v[i].time]=curr;
    }
    for(i=1;i<=t;i++)
        dp_tank[i]=max(dp_tank[i],dp_tank[i-1]);
    for(i=1;i<=t;i++)
    {
        dp_time[i]=dp_time[i-1];
        for(j=1;j<=i;j++)
            dp_time[i]=max(dp_time[i],dp_time[i-j]+dp_tank[j]);
    }
    fout<<dp_time[t];
    fin.close();
    fout.close();
    return 0;
}