Pagini recente » Cod sursa (job #1310455) | Cod sursa (job #1857955) | Cod sursa (job #476080) | Istoria paginii runda/quarter_2018 | Cod sursa (job #796682)
Cod sursa(job #796682)
#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
int n, K, Ttotal, dp[nmax], cat[Tmax];
pair<int, int> v[nmax];
multiset<int> S;
void citeste(){
f >> n >> K >> Ttotal;
for(int i=1; i<=n; ++i){
int x, y;
f >> x >> y;
v[i] = make_pair(y,x);
}
sort(v+1, v+n+1);
}
void preprocesare(){
//sunt sortate dupa timp; => o sa am nevoie pentru fiecare i de cele mai bune K produse
int sum = 0;
for(int i=1; i<=n; ++i){
sum += v[i].second;//nr de pesti de la plsa i;
S.insert(v[i].second);
if (i > K){
sum -= *S.begin();
S.erase( S.begin() );
}
cat[v[i].first] = sum;//aici tin minte maximul pana la momentul v[i].first
}
for(int i=1; i<Tmax; ++i){
cat[i] = max(cat[i], cat[i-1]);
}
}
void rezolva(){
//fac un dp[i] = nr maxim de pesti pe care ii pot prinde daca ultima plasa o scot la momentul i
//o sa mai am nevoie si de un cat[i] = X, cati pesti pot prinde daca scot plasa i(adica ea e cea mai mare();
//schimb putin cand ma uit in spate ; T[i] <= 1000 => nu are rost sa ma duc printre toate cele n plase si ajunge printre
//printre cele 1000
preprocesare();
dp[0] = 0;
for(int i=1; i<=Ttotal; ++i){
int 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);
}
//cout << dp[Ttotal] << "\n";
g << dp[Ttotal] << "\n";
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}