Submission #1870746


Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <fstream>
#include <bitset>
#include <time.h>
#include <tuple>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = 1e12;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define rep(i,N) for(ll i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1
#define MAX_N 100100

ll sq(ll num) { return num*num; }
ll mod_pow(ll x, ll n) {
	if (n == 0)return 1;
	if (n == 1)return x%MOD;
	ll res = sq(mod_pow(x, n / 2));
	res %= MOD;
	if (n % 2 == 1) {
		res *= x;
		res %= MOD;
	}
	return res;
}
ll mod_add(ll a, ll b) { return (a + b) % MOD; }
ll mod_sub(ll a, ll b) { return (a - b + MOD) % MOD; }
ll mod_mul(ll a, ll b) { return a*b % MOD; }

ll N, W;
ll w[110], v[110];
ll dp[110][110][500];

int main() {
	cin >> N >> W;
	ll buf = 0;
	rep(i, N) {
		cin >> w[i] >> v[i];
		if (i == 0)buf = w[i];
		w[i] -= buf;
	}
	rep(i, N) {
		rep(j, 110) {
			rep(k, 500) {
				ll ww = buf*j + k;
				ww += buf + w[i];
				ll nj = ww / buf;
				ll nk = ww - nj*buf;
				if (ww <= W) {
					dp[i + 1][nj][nk]
						= max(dp[i + 1][nj][nk],
							dp[i][j][k] + v[i]);
				}
				dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k]);
			}
		}
	}
	ll ans = 0;
	rep(i, 110) {
		rep(j, 500) {
			if (i*buf + j <= W) {
				ans = max(ans, dp[N][i][j]);
			}
		}
	}
	//rep(k, N + 1) {
	//	rep(i, 10) {
	//		rep(j, 3) {
	//			cout << dp[k][i][j] << " ";

	//		}
	//		cout << endl;
	//	}
	//	cout << endl;
	//}
	cout << ans << endl;
}

Submission Info

Submission Time
Task D - Simple Knapsack
User jimmy
Language C++14 (GCC 5.4.1)
Score 400
Code Size 2124 Byte
Status AC
Exec Time 71 ms
Memory 45056 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 4
AC × 16
Set Name Test Cases
Sample example0, example1, example2, example3
All antigreedy0, antigreedy1, antigreedy2, example0, example1, example2, example3, quarter0, quarter1, quarter2, rand0, rand1, rand2, smallw0, smallw1, smallw2
Case Name Status Exec Time Memory
antigreedy0 AC 71 ms 44928 KB
antigreedy1 AC 71 ms 45056 KB
antigreedy2 AC 71 ms 44928 KB
example0 AC 3 ms 3968 KB
example1 AC 3 ms 3968 KB
example2 AC 3 ms 3968 KB
example3 AC 3 ms 3968 KB
quarter0 AC 40 ms 44928 KB
quarter1 AC 36 ms 44928 KB
quarter2 AC 25 ms 44928 KB
rand0 AC 3 ms 3968 KB
rand1 AC 9 ms 22400 KB
rand2 AC 6 ms 12160 KB
smallw0 AC 17 ms 44928 KB
smallw1 AC 17 ms 44928 KB
smallw2 AC 18 ms 44928 KB