Pagini recente » Cod sursa (job #1032523) | Cod sursa (job #2741210) | Cod sursa (job #3216083) | Cod sursa (job #2353023) | Cod sursa (job #1895272)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("lupu.in");
ofstream out("lupu.out");
const int NMax = 100000 + 5;
// rezolvare cu programare dinamica, nu poate lua punctaj maxim din cauza
// problemelor de eficienta si memorie
int N,X,L;
long long dp[NMax][2002];
// dp[i][j] = cantitatea maxima de lana care se poate obtine din primele i oi pana in momentul j
// unde momentele se iau in ordine inversa si inseamna numarul maxim de miscari pe care le face lupul
struct elem {
int dist,val,step;
}v[NMax];
// v[i].step = momentul minim (luat in ordine inversa) din care oaia i poate fi luata de lup
bool cmp (elem a,elem b) {
if (a.step == -1) {
return false;
}
if (b.step == -1) {
return true;
}
return a.dist<b.dist;
}
const int strMax = 100005 * 30;
char str[strMax];
int pos = 0;
// parsare
int getNumber() {
int nr = 0;
while (!('0'<=str[pos] && str[pos]<='9')) {
++pos;
}
while ('0'<=str[pos] && str[pos]<='9') {
nr = nr * 10 + str[pos++] - '0';
}
return nr;
}
int main() {
in.getline(str,strMax,'%');
N = getNumber();
X = getNumber();
L = getNumber();
int maxStep = 0;
for (int i=1;i<=N;++i) {
v[i].dist = getNumber();
v[i].val = getNumber();
v[i].step = (v[i].dist > X) ? -1 : (X - v[i].dist)/L;
if (maxStep < v[i].step) {
maxStep = v[i].step;
}
}
// se inverseaza momentele
++maxStep; // pentru a fi nenule
for (int i=1;i<=N;++i) {
v[i].step = maxStep - v[i].step;
}
sort(v+1,v+N+1,cmp);
int minDist = v[1].dist;
if (minDist > X) {
out<<0;
return 0;
}
for (int j=1;j<=maxStep;++j) {
for (int i=1;i<=N;++i) {
// daca oaia i poate fi luata in momentul j
bool available = (j>=v[i].step) ? true : false;
dp[i][j] = dp[i-1][j];
if (available && dp[i][j] < dp[i-1][j-1] + v[i].val) {
dp[i][j] = dp[i-1][j-1] + v[i].val;
}
}
}
out<<dp[N][maxStep];
return 0;
}