Pagini recente » Cod sursa (job #548660) | Cod sursa (job #1255895) | Cod sursa (job #2892960) | Cod sursa (job #1390459) | Cod sursa (job #22226)
Cod sursa(job #22226)
#include <stdio.h>
#include <vector>
#include <iterator>
using namespace std;
#define in "lupu.in"
#define out "lupu.out"
vector< vector<int> > a;
vector<int> timp;
vector<int> val, x;
vector<bool> sel;
int n, d, t;
int main()
{
int tmax=0;
freopen(in,"r",stdin);
freopen(out,"w",stdout);
scanf("%d%d%d",&n,&t,&d);
val.resize(n+1);
x.resize(n+1);
a.resize(3);
timp.resize(n+1);
sel.resize(n+1);
for ( int i = 1; i <= n; i++ )
{
scanf("%d%d",&x[i],&val[i]);
if ( x[i] > t ) timp[i] = -1;
else timp[i] = (t-x[i])/d;
if ( tmax < (t-x[i])/d ) tmax = (t-x[i])/d;
}
for ( int i = 1; i <= 2; i++ ) a[i].resize(tmax+1);
for ( int i = 0; i <= 1; i++ )
for ( int j = 0; j <= tmax; j++ )
a[i][j] = 0;
int poz, maxim;
for ( int i = 1; i <= n; i++ )
if ( a[0][0] < val[i] && timp[i] > 0 ) a[0][0] = val[i], poz = i;
sel[poz] = 1;
for ( int j = 1; j <= tmax; j++ )
{
maxim = 0;
for ( int i = 1; i <= n; i++ )
{
if ( sel[i] || timp[i] < j || timp[i] == -1 ) continue;
if ( a[1][j] < a[0][j-1] + val[i] )
{
a[1][j] = a[0][j-1] + val[i];
if ( maxim < a[1][j] ) maxim = a[1][j], poz = i;
}
}
a[0][j] = maxim;
sel[poz] = 1;
}
printf("%d",a[0][tmax]);
}