# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
934499 | 2024-02-27T13:11:38 Z | TIN | Kas (COCI17_kas) | C++17 | 157 ms | 1784 KB |
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int INF = 2e9; void Task() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout << fixed << setprecision(9); if (fopen("test.inp","r")) { freopen("test.inp","r",stdin); freopen("test.out","w",stdout); } } void Solve() { //Your Code int n; cin >> n; vector<int> dp1, dp2; dp1.resize(MAXN, INF); dp2.resize(MAXN); dp1[0] = 0; int sum = 0; for (int j = 0; j < n; j++) { int x; cin >> x; sum += x; dp2 = dp1; dp1.assign(dp1.size(), INF); for (int v = 0; v < MAXN; ++v) { if (x + v < MAXN) dp1[x + v] = min(dp1[x + v], dp2[v]); dp1[abs(v - x)] = min(dp1[abs(v - x)], dp2[v]); dp1[v] = min(dp1[v], dp2[v] + x); } } cout << (sum - dp1[0]) / 2 + dp1[0] << '\n'; } int main() { Task(); Solve(); cerr << "\nTime run: " << 1000*clock()/CLOCKS_PER_SEC << "ms"; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1112 KB | Output is correct |
2 | Correct | 4 ms | 1116 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1116 KB | Output is correct |
2 | Correct | 5 ms | 1256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1116 KB | Output is correct |
2 | Correct | 4 ms | 1116 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1248 KB | Output is correct |
2 | Correct | 5 ms | 1116 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 1116 KB | Output is correct |
2 | Correct | 5 ms | 1252 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 1116 KB | Output is correct |
2 | Correct | 16 ms | 1256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 1256 KB | Output is correct |
2 | Correct | 16 ms | 1116 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 64 ms | 1244 KB | Output is correct |
2 | Correct | 81 ms | 1236 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 92 ms | 1116 KB | Output is correct |
2 | Correct | 124 ms | 1368 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 142 ms | 1784 KB | Output is correct |
2 | Correct | 157 ms | 1232 KB | Output is correct |