# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
245693 |
2020-07-07T08:03:42 Z |
Vimmer |
Kas (COCI17_kas) |
C++14 |
|
625 ms |
392848 KB |
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 200100
#define M ll(998244353)
#define inf 1e9 + 1e9
using namespace std;
//using namespace __gnu_pbds;
typedef long double ld;
typedef long long ll;
typedef short int si;
typedef array <int, 3> a3;
//typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int f[501][N], bl = 100000;
int main()
{
//freopen("input.txt", "r", stdin); //freopen("output4.txt", "w", stdout);
ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n;
cin >> n;
int c[n], sm = 0;
for (int i = 0; i < n; i++) {cin >> c[i]; sm += c[i];}
sort(c, c + n);
reverse(c, c + n);
for (int i = 0; i <= n; i++)
for (int j = 0; j < N; j++) f[i][j] = -1e9;
f[0][bl] = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < N; j++)
{
if (f[i][j] == -1e9) continue;
if (f[i][j] > f[i + 1][j]) f[i + 1][j] = f[i][j];
if (f[i][j] + c[i] > f[i + 1][j + c[i]]) f[i + 1][j + c[i]] = f[i][j] + c[i];
if (f[i][j] > f[i + 1][j - c[i]]) f[i + 1][j - c[i]] = f[i][j];
}
cout << sm - 2 * f[n][bl] + f[n][bl];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
8960 KB |
Output is correct |
2 |
Correct |
11 ms |
8960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
8960 KB |
Output is correct |
2 |
Correct |
11 ms |
8960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
8960 KB |
Output is correct |
2 |
Correct |
13 ms |
9728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
10496 KB |
Output is correct |
2 |
Correct |
14 ms |
11264 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
11392 KB |
Output is correct |
2 |
Correct |
14 ms |
11392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
28544 KB |
Output is correct |
2 |
Correct |
31 ms |
32496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
36352 KB |
Output is correct |
2 |
Correct |
40 ms |
40312 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
204 ms |
157840 KB |
Output is correct |
2 |
Correct |
197 ms |
196856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
259 ms |
236024 KB |
Output is correct |
2 |
Correct |
429 ms |
314616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
539 ms |
353528 KB |
Output is correct |
2 |
Correct |
625 ms |
392848 KB |
Output is correct |