Pagini recente » Istoria paginii runda/9a.info/clasament | Cod sursa (job #880065) | Cod sursa (job #2461105) | Cod sursa (job #1856663) | Cod sursa (job #1895176)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("lupu.in");
ofstream out("lupu.out");
const int NMax = 100000 + 5;
int N,X,L;
long long dp[NMax][1002];
struct elem {
int dist,val,step;
}v[NMax];
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;
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 MAX_STEP = 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 (MAX_STEP < v[i].step) {
MAX_STEP = v[i].step;
}
}
++MAX_STEP;
for (int i=1;i<=N;++i) {
v[i].step = MAX_STEP - v[i].step;
}
sort(v+1,v+N+1,cmp);
/*
for (int i=1;i<=N;++i) {
cout<<v[i].dist<<' '<<v[i].val<<' '<<v[i].step<<'\n';
}
cout<<"\n\n";
//*/
int minDist = v[1].dist;
if (minDist > X) {
out<<0;
return 0;
}
/*
for (int i=1;i<=N;++i) {
for (int j=1;j<=MAX_STEP;++j) {
cout<<dp[i][j]<<' ';
}
cout<<'\n';
}
cout<<'\n';
//*/
for (int j=1;j<=MAX_STEP;++j) {
for (int i=1;i<=N;++i) {
bool available = (v[i].step<=j) ? 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;
}
}
}
/*
for (int i=1;i<=N;++i) {
for (int j=1;j<=MAX_STEP;++j) {
cout<<dp[i][j]<<' ';
}
cout<<'\n';
}
cout<<'\n';
//*/
out<<dp[N][MAX_STEP];
return 0;
}