Submission #12183786

---

Source Code Expand

/*---> 21 April 2020 <--- > 04:42:50 <---*/
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("unroll-loops")
// #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
//#pragma GCC target ("sse4")
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
//template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define int long long
#define F first
#define S second
#define mod 1000000007
#define inf (int)1e12+5
#define sz(x) (int)x.size()
#define PI 3.141592653589793238510
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define __ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define vi vector<int>
#define vpii vector<pair<int,int> > 
#define vvi vector<vector<int> >
#define PRINT_TIME cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s." <<endl;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename   enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
typedef long double ld;
typedef pair<int,int> pii;
///////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////
const int N=1e2+5;
int n,W;
int v[N],w[N],dp[N][100001];
int solve(int ind,int V){
    if(V<0)
        return inf;
    int &ans=dp[ind][V];
    if(ans!=-1)
        return ans;
    if(ind==n){
        if(V==0)
            return ans=0;
        else
            return ans=inf;
    }
    else
        return ans=min(w[ind]+solve(ind+1,V-v[ind]),solve(ind+1,V));
}
int32_t main(){__
    cin>>n>>W;
    for(int i=0;i<n;i++){
        cin>>w[i]>>v[i];
    }
    memset(dp,-1,sizeof dp);
    for(int i=100000;i>=0;i--){
        if(solve(0,i)<=W)
            return cout<<i<<"\n",0;
    }
return 0;
}

Submission Info

Judge Result