Submission #2663955

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

typedef long long int ll;

#define FOR(i,n,m) for(ll i=(ll)(m);i<(ll)(n);++i)
#define REP(i,n) FOR(i,n,0)
#define IREP(i,n) for(ll i=(ll)(n);i>=0;--i)

const ll MOD = 1000000007;

using namespace std;

ll dp[105][105][305];
pair<ll, ll> g[105];


int main()
{
	ll N, W;
	cin >> N >> W;

	ll w0 = 0;
	int offset = 0;
	REP(i, N)
	{
		ll w, v;
		cin >> g[i].first >> g[i].second;
		if (i == 0)
		{
			w0 = g[i].first;
		}
		g[i].first -= w0;
		offset += g[i].first;
	}

	//memset(dp, 0, sizeof(dp));

	REP(i, N)
	{
		for (int j = 1; j <= i + 1; ++j)
		{
			REP(k, j * 3 + 1)
			{
				ll wi = g[i].first;
				if (k - wi < 0 || j*w0 + k>W)
				{
					dp[i + 1][j][k] = dp[i][j][k];
					continue;
				}
				dp[i + 1][j][k] = std::max(dp[i][j][k], dp[i][j - 1][k - wi] + g[i].second);
			}
		}
	}

	ll max = 0;
	REP(i, N + 1)
	{
		REP(j, offset + 1)
		{
			max = std::max(max, dp[N][i][j]);
		}
	}

	cout << max << endl;
	return 0;
}

Submission Info

Judge Result