Submission #3772839

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define REP(i, n) FOR(i, 0, n)
#define RFOR(i, a, b) for(int i=(a);i>=(b);i--)
#define RREP(i, n) RFOR(i, n, 0)
#define MFOR(i, m) for(auto i=(m).begin();i!=(m).end();i++)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((int)(x).size())

typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;

const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1 << 30;

template<typename T>
void printv(vector<T> const& s) {
  REP(i, SZ(s)) {
    cout << s[i] << " ";
  }
  cout << endl;
}

int main () {
  cin.tie(0);
  cout << setprecision(10);

  int n, W; cin >> n >> W;
  vll w(n), v(n);
  REP(i, n) {
    cin >> w[i] >> v[i];
  }

  vector<map<int, ll>> dp(n);
  dp[0][w[0]] = v[0];
  REP(i, n-1) {
    MFOR(j, dp[i]) {
      dp[i+1][j->first] = max(dp[i+1][j->first], j->second);
      dp[i+1][j->first + w[i+1]] = max(dp[i+1][j->first + w[i+1]], j->second + v[i+1]);
    }
    dp[i+1][w[i+1]] = max(dp[i+1][w[i+1]], v[i+1]);
  }

  ll ma = 0;
  MFOR(j, dp[n-1]) {
    if(j->first > W) break;
    ma = max(ma, j->second);
  }
  cout << ma << endl;
}

Submission Info

Judge Result