oj.uz

Submission #380674

# Submission time Handle Problem Language Result Execution time Memory
380674 2021-03-22T19:10:39 Z saarang123 Knapsack (NOI18_knapsack) C++17
0 / 100
 3 ms 748 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 1e15, N = 2002;
vector<array<int, 2>> a[N];
int ans = 0;
signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("C:/Users/shriya-student/Documents/competitive programming/newproj/input.txt", "r", stdin);
    freopen("C:/Users/shriya-student/Documents/competitive programming/newproj/output.txt", "w", stdout);
    #endif
    int n, s;
    cin >> s >> n;
    for(int w, c, k, i = 0; i < n; i++) {
    	cin >> c >> w >> k;
    	k = min(k, s / w);
    	a[w].push_back({c, k});
    }
    vector<array<int, 2>> costs;
    for(int i = 1; i <= s; i++) sort(a[i].begin(), a[i].end(), greater<>());
    for(int i = 1; i <= s; i++) {
    	int left = s / i;
    	for(auto x : a[i]) {
    		int c = x[0], k = x[1];
    		for(int j = 0; j < k && left > 0; j++, left--) {
    			costs.push_back({i, c});
    		}
    	}
    }
    n = costs.size();
    vector<vector<int>> dp(n + 2, vector<int>(s + 2, -inf));
    dp[0][0] = 0;
    for(int i = 1; i <= n; i++) {
    	for(int j = 0; j <= s; j++) {
    		dp[i][j] = dp[i - 1][j];
    		if(j - costs[i - 1][0] >= 0)
    			dp[i][j] = max(dp[i][j], dp[i - 1][j - costs[i - 1][0]] + costs[i - 1][1]);
    		ans = max(ans, dp[i][j]);
    	}
    }
    cout << ans << '\n';
    return 0;
}

Compilation message

knapsack.cpp: In function 'int main()':
knapsack.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   12 |     freopen("C:/Users/shriya-student/Documents/competitive programming/newproj/input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   13 |     freopen("C:/Users/shriya-student/Documents/competitive programming/newproj/output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 748 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 748 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 748 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 748 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 748 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -