Submission #5554307

---

Source Code Expand

#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<deque>
#include<regex>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>

#define rep(i, n) for(int i=0;i<n;i++)

typedef int long long ll;
using namespace std;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const ll MOD = 1e9 + 7;
static const int MAX = 100;
static const int INF = (1 << 23);

int main() {
    ll N,W;
    cin>>N>>W;
    ll v[N],w[N];
    rep(i,N){
        cin>>v[i]>>w[i];
    }
    map<ll,ll> m;
    rep(i,N){
        if(w[i]>W){
        }else{
            map<ll,ll> ma;
            ma=m;
            if(m.size()!=0) {
                for (auto &&a:m) {
                    if (a.first + w[i] <= W) {
                        ma[a.first + w[i]] = max(ma[a.first + w[i]], ma[a.first] + v[i]);
                    }
                }
                ma[w[i]] = max(v[i], ma[w[i]]);
                m = ma;
            }else{
                m[w[i]]=v[i];
            }

        }

    }
    ll ans=0;
    for(auto &&a:m){
        if(a.first<=W&&a.second>ans){ans=a.second;}
    }
    cout<<ans<<endl;




    return 0;
}

Submission Info

Judge Result