Cod sursa(job #1074422)

Utilizator sleepaholicNeculaescu Theodor sleepaholic Data 7 ianuarie 2014 17:33:12
Problema Peste Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>
using namespace std;
ifstream f("peste.in");
ofstream g("peste.out");
#define nmax 50005
#define Tmax 1005
#define ll long long
#define Cifmax 5000005
int n, K, Ttotal;
ll dp[nmax], cat[Tmax];
pair<int, int> v[nmax];
multiset<int> Heap;
int poz;
char S[Cifmax];
void buf( int &nr){
nr = 0;
for(; S[poz]<'0' || S[poz]>'9'; poz++);
for(; S[poz]>='0' && S[poz]<='9'; poz++){
nr = nr * 10 + (S[poz] - '0');
}
}
void citeste(){
f.getline(S, Cifmax, EOF);
 
buf(n); buf(K); buf(Ttotal);
for(int i=1; i<=n; ++i){
int x, y;
 
buf(x); buf(y);
v[i] = make_pair(y,x);
}
sort(v+1, v+n+1);
}
struct cmp{
bool operator() (const int &A, const int &B){
return A > B;
}
};
void preprocesare(){
priority_queue< int, vector<int>, cmp> Q;
 
ll sum = 0LL;
for(int i=1; i<=n; ++i){
sum += v[i].second;
 
Q.push(v[i].second);
if (i > K){
sum -= 1LL*(Q.top());
 
Q.pop();
}
cat[v[i].first] = sum;
}
for(int i=1; i<Tmax; ++i){
cat[i] = max(cat[i], cat[i-1]);
}
}
void rezolva(){
 
preprocesare();
dp[0] = 0LL;
for(int i=1; i<=Ttotal; ++i){
ll Max = 0;
for(int j=0; j<Tmax && i>=j; ++j){
Max = max(Max, dp[i-j] + cat[j]);
}
dp[i] = max(dp[i-1],Max);
}
 
g << dp[Ttotal] << "\n";
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}