Pagini recente » Monitorul de evaluare | Borderou de evaluare (job #1195745) | Cod sursa (job #2940569)
#include <bits/stdc++.h>
using namespace std;
#define FMOD(x) if(x >= MOD) x-= MOD;
using ll = long long;
using ull = uint64_t;
using pi = pair<int, int>;
using ti = tuple<int, int, int>;
using tl = tuple<ll, ll, ll>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pi>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpl = vector<pl>;
using vti = vector<ti>;
using vtl = vector<tl>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvpi = vector<vpi>;
using vvpil = vector<vpil>;
using vvpli = vector<vpli>;
using vvpl = vector<vpl>;
using vvti = vector<vti>;
using vvtl = vector<vtl>;
#if 1
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
#define cin fin
#define cout fout
#endif
const int nmx = 5e3 + 1;
const int gmx = 1e4 + 1;
int dp[2][gmx]; // i - element, j - suma curenta
int w[nmx],p[nmx];
int main()
{
int n,g;
cin >> n >> g;
for(int i=1;i<=n;i++)
cin >> w[i] >> p[i];
for(int i=1,k=0;i<=n;i++,k=!k)
for(int j=1;j<=g;j++)
{
dp[k][j] = max(dp[k][j], dp[!k][j]);
if(j-w[i]>=0)
dp[k][j] = max(dp[k][j], dp[!k][j-w[i]] + p[i]);
}
cout << dp[(n+1)%2][g];
}