oj.uz

Submission #735243

# Submission time Handle Problem Language Result Execution time Memory
735243 2023-05-03T18:23:45 Z danilovict2 Knapsack (NOI18_knapsack) C++14
73 / 100
 144 ms 262144 KB 
#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];
     
    void solve(){
    	int n,s;
    	cin>>s>>n;
    	int v[n], w[n], k[n];
    	forn(i,n){
    		cin>>v[i]>>w[i]>>k[i];
    	}
    	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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 2 ms 980 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 980 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 2 ms 980 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 3 ms 980 KB Output is correct
13 Correct 1 ms 980 KB Output is correct
14 Correct 1 ms 980 KB Output is correct
15 Correct 1 ms 1108 KB Output is correct
16 Correct 2 ms 980 KB Output is correct
17 Correct 1 ms 980 KB Output is correct
18 Correct 1 ms 980 KB Output is correct
19 Correct 2 ms 980 KB Output is correct
20 Correct 1 ms 1108 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 1 ms 980 KB Output is correct
12 Correct 2 ms 980 KB Output is correct
13 Correct 1 ms 980 KB Output is correct
14 Correct 1 ms 980 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 3 ms 980 KB Output is correct
17 Correct 1 ms 980 KB Output is correct
18 Correct 1 ms 980 KB Output is correct
19 Correct 1 ms 1108 KB Output is correct
20 Correct 2 ms 980 KB Output is correct
21 Correct 1 ms 980 KB Output is correct
22 Correct 1 ms 980 KB Output is correct
23 Correct 2 ms 980 KB Output is correct
24 Correct 1 ms 1108 KB Output is correct
25 Correct 1 ms 724 KB Output is correct
26 Correct 144 ms 1112 KB Output is correct
27 Correct 1 ms 980 KB Output is correct
28 Correct 1 ms 980 KB Output is correct
29 Correct 1 ms 1108 KB Output is correct
30 Correct 2 ms 1108 KB Output is correct
31 Correct 2 ms 1108 KB Output is correct
32 Correct 1 ms 980 KB Output is correct
33 Correct 2 ms 980 KB Output is correct
34 Correct 2 ms 980 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 1 ms 980 KB Output is correct
12 Correct 2 ms 980 KB Output is correct
13 Correct 1 ms 980 KB Output is correct
14 Correct 1 ms 980 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 3 ms 980 KB Output is correct
17 Correct 1 ms 980 KB Output is correct
18 Correct 1 ms 980 KB Output is correct
19 Correct 1 ms 1108 KB Output is correct
20 Correct 2 ms 980 KB Output is correct
21 Correct 1 ms 980 KB Output is correct
22 Correct 1 ms 980 KB Output is correct
23 Correct 2 ms 980 KB Output is correct
24 Correct 1 ms 1108 KB Output is correct
25 Correct 1 ms 724 KB Output is correct
26 Correct 144 ms 1112 KB Output is correct
27 Correct 1 ms 980 KB Output is correct
28 Correct 1 ms 980 KB Output is correct
29 Correct 1 ms 1108 KB Output is correct
30 Correct 2 ms 1108 KB Output is correct
31 Correct 2 ms 1108 KB Output is correct
32 Correct 1 ms 980 KB Output is correct
33 Correct 2 ms 980 KB Output is correct
34 Correct 2 ms 980 KB Output is correct
35 Runtime error 111 ms 262144 KB Execution killed with signal 9
36 Halted 0 ms 0 KB -