# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
516990 | 2022-01-22T10:35:54 Z | DiTenix | Knapsack (NOI18_knapsack) | C++17 | 1000 ms | 376 KB |
#define eb emplace_back #define pb push_back #define pii pair<int,int> #define sz(x) int((x).size()) #define ALL(x) (x).begin(),(x).end() #define ln cout << '\n' #define REP(i, a) for (int i = 0; i < int(a); i++) #define FOR(i, a) for (int i = 1; i <= int(a); i++) #define MEM(a,b) memset((a),(b),sizeof(a)) const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; using namespace std; #include <bits/stdc++.h> using ll = long long; using vi = vector<int>; template<typename T> void rd(vector<T> &a) {for (auto &ele : a) cin >> ele;} template<typename T> void writeln(vector<T> &a) {for (auto &ele : a) cout << ele << ' '; cout << "\n";} #if __cplusplus > 201402L template<typename... Args> void rd(Args&... args) {((cin >> args), ...);} template<typename... Args> void write(Args... args) {((cout << args << " "), ...);} template<typename... Args> void writeln(Args... args) {((cout << args << " "), ...); cout << "\n";} #endif const int maxn = 1e6 + 5; ll v[maxn], w[maxn], k[maxn]; ll dp[2][2005]; signed main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif cin.tie(0); cout.tie(0); ios::sync_with_stdio(false); // int t;cin >> t;while(t--) solve(); int n, S; cin >> S >> n; FOR(i, n) { cin >> v[i] >> w[i] >> k[i]; } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= S; ++j) { dp[1][j] = dp[0][j]; for (int c = 1; c * w[i] <= j && c <= k[i]; ++c) { dp[1][j] = max(dp[1][j], dp[0][j - c * w[i]] + c * v[i]); } } swap(dp[1], dp[0]); } ll res = 0; for (int i = 0; i <= S; ++i) { res = max(res, dp[0][i]); } writeln(res); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1090 ms | 364 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1079 ms | 376 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1079 ms | 376 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1090 ms | 364 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1090 ms | 364 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |