Cod sursa(job #3214932)
Utilizator | Serban Carole SerbanCarole | Data | 14 martie 2024 16:16:16 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.58 kb |
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
using pii = pair<int,int>;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
const int nmax = 1e4 + 1;
int dp[nmax] , n , w , p , g;
signed main()
{
cin >> n >> g;
for(int i = 1 ; i <= g ; ++i) dp[i] = -1e9;
for(int i = 1 ; i <= n ; ++i)
{
cin >> w >> p;
for(int j = g ; j >= w ; --j)
{
dp[j] = max(dp[j],dp[j-w] + p);
}
}
for(int i = 2 ; i <= g ; ++i) dp[i] = max(dp[i],dp[i-1]);
cout << dp[g];
return 0;
}