Pagini recente » Clasament nimic_suspect. | Cod sursa (job #1073907) | Clasament preoji_3 | Cod sursa (job #2421403) | Cod sursa (job #796185)
Cod sursa(job #796185)
#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 ll long long
int n, K, Ttotal, dp[nmax], cat[nmax];
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[i] = sum;
}
}
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();
preprocesare();
dp[0] = 0;
for(int i=1; i<=Ttotal; ++i){
int Max = 0;
for(int j=1; j<=n && i>=v[j].first; ++j){
if (i - v[j].first >= 0)
Max = max(Max, dp[ i- v[j].first ] + cat[j]);
else Max = max(Max, 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;
}