Pagini recente » Cod sursa (job #254652) | Borderou de evaluare (job #565556) | Cod sursa (job #1631148) | Cod sursa (job #2416465) | Cod sursa (job #22505)
Cod sursa(job #22505)
#include <stdio.h>
#include <vector>
#include <iterator>
using namespace std;
#define in "lupu.in"
#define out "lupu.out"
vector< vector<unsigned int> > a;
vector<unsigned int> timp;
vector<unsigned int> val;
vector<bool> sel;
unsigned int n, d, t;
int main()
{
int tmax=0, x;
freopen(in,"r",stdin);
freopen(out,"w",stdout);
scanf("%u%u%u",&n,&t,&d);
val.resize(n+1);
a.resize(2);
timp.resize(n+1);
sel.resize(n+1);
int i, j;
for ( i = 1; i <= n; i++ )
{
scanf("%u%u",&x,&val[i]);
if ( x > t ) timp[i] = -1;
else timp[i] = (t-x)/d;
if ( tmax < (t-x)/d ) tmax = (t-x)/d;
}
for ( i = 0; i <= 1; i++ ) a[i].resize(tmax+1);
int poz, maxim;
for ( i = 1; i <= n; i++ )
if ( a[0][tmax] < val[i] && timp[i] >= tmax ) a[0][tmax] = val[i], poz = i;
sel[poz] = 1;
for ( j = tmax-1; j >= 0; j-- )
{
maxim = 0;
for ( 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;
}
/* for ( int j = 0; j <= tmax; j++ )
{
for ( int i = 0; i <= 1; i++ )
{
printf("%d ", a[i][j] );
}
printf("\n");
}*/
//for ( int i = 1; i <= n; i++ ) printf("%d ", );
printf("%u",a[0][0]);
}
/*
#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;
vector<bool> sel;
int n, d, t;
int main()
{
int tmax=0, x;
freopen(in,"r",stdin);
freopen(out,"w",stdout);
scanf("%d%d%d",&n,&t,&d);
val.resize(n+1);
a.resize(2);
timp.resize(n+1);
sel.resize(n+1);
for ( int i = 1; i <= n; i++ )
{
scanf("%d%d",&x,&val[i]);
if ( x > t ) timp[i] = -1;
else timp[i] = (t-x)/d;
if ( tmax < (t-x)/d ) tmax = (t-x)/d;
}
for ( int i = 0; i <= 1; i++ ) a[i].resize(tmax+1);
int poz, maxim;
for ( int i = 1; i <= n; i++ )
if ( a[0][tmax] < val[i] && timp[i] >= tmax ) a[0][tmax] = val[i], poz = i;
sel[poz] = 1;
for ( int j = tmax-1; j >= 0; 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;
}
/* for ( int j = 0; j <= tmax; j++ )
{
for ( int i = 0; i <= 1; i++ )
{
printf("%d ", a[i][j] );
}
printf("\n");
}
//for ( int i = 1; i <= n; i++ ) printf("%d ", );
printf("%d",a[0][0]);
}
*/