Submission #735245

#	Time	Username	Problem	Language	Result	Execution time	Memory
735245		danilovict2	Knapsack (NOI18_knapsack)	C++14	73 / 100	225 ms	262144 KiB

knapsack

    #include <bits/stdc++.h>
        using namespace std;
         
        #define ll long long
        #define ull unsigned long long
        #define pb push_back
        #define pii pair<int, int>
        #define vi vector<int>
        #define vii vector<pair<int, int>>
        #define mp make_pair
        #define sz(a) a.size()
        #define MOD 1000000007
        #define forn(i, n) for (int i = 0; i < n; ++i)
        #define INF 1e18
        const vector<pair<int, int>> dirs1 = {{-1, -1}, {-1, 1}, {1, 1}, {1, -1}, {-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        const vector<pair<int, int>> dirs2 = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        bool sortbysec(const pair<int, int> &a, const pair<int, int> &b) { return (a.second < b.second); }
        const int maxN = 100001;
         
        int dp[maxN][2001];
         vi v,w,k;
        void solve(){
        	int n,s;
        	cin>>s>>n;
        	forn(i,n){
              	int x,y,z;
        		cin>>x>>y>>z;
              	v.pb(x), w.pb(y), k.pb(z);
        	}
        	dp[0][0] = 0;
        	for(int i=1;i<=n;++i){
        		for(int j=1;j<=s;++j){
        			dp[i][j] = dp[i-1][j];
        			for(int t=1;t<=k[i-1];++t){
        				if(j >= t*w[i-1])dp[i][j] = max(dp[i][j], dp[i-1][j-t*w[i-1]] + v[i-1]*t);
        				else break;
                    }
        		}
        	}
        	cout<<dp[n][s]<<"\n";
        }
         
        int main(void){
        	ios::sync_with_stdio(0);
        	cin.tie(0);
        	cout.tie(0);
        	solve();
        	return 0;
        }

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 27