# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
474193 | 2021-09-17T09:30:09 Z | kingline | Bootfall (IZhO17_bootfall) | C++17 | 1000 ms | 344 KB |
#pragma GCC optimize ("Ofast") #pragma GCC optimize ("unroll-loops") #pragma GCC target("avx,avx2,fma") #include <iostream> #include <stdio.h> #include <algorithm> #include <cstdio> #include <cstdlib> #include <iomanip> #include <cmath> #include <vector> #include <string> #include <stack> #include <map> #include <set> #include <queue> #define pb push_back #define F first #define mp make_pair #define S second #define pii pair <int, int > #define pll pair <long long, long long > #define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define all(data) data.begin() , data.end() #define endl '\n' #define bo cout << "OK" << endl; #define file(data) freopen(data".in", "r", stdin); freopen(data".out", "w", stdout); //freopen("nenokku_easy.in", "r", stdin); //freopen("nenokku_easy.out", "w", stdout); #define int long long using namespace std; typedef long double ld; typedef long long ll; typedef unsigned long long ull; const ll N = 1e6 + 5; const ll mod = 1e9 + 7; const ll INF = 1e10; const ll M = (1 << 17) + 5; const ll LL = 1; const ll p = 31; bool ok; ll q, n, m, k, a[N]; int dp[500 * 500], sum, mn = 501; string s, s1, s2; bool check2(vector < int > &v, int ign) { int sum1 = sum; sum += a[ign]; if(sum1 % 2 == 0) { sum1 /= 2; dp[0] = 1; for(int i = 1; i <= sum1; i++) { dp[i] = 0; } for (int i = 0; i < v.size(); ++i) { if(i == ign) continue; for (int j = sum1; j >= 0; --j) { if (dp[j] == 1 && j + v[i] <= sum1) { dp[j + v[i]] = 1; if(j + v[i] == sum1) return 1; } } }/* cout << "Sum: " << sum1 * 2 << "\n"; for (int i = 0; i < v.size(); ++i) { cout << v[i] << " "; } cout << " --> " << dp[sum1] << "\n";*/ } return 0; } vector < int > v; bool check() { //a[0] = v[0] = val; //cout << "Val: " << val << "\n"; for(int i = 0; i <= n; i++) { /*for(int j = 0; j <= n; j++) { if(i != j) { v.pb(a[j]); //cout << a[j] << " "; } }*/ //cout << endl; sum -= a[i]; if(!check2(v, i)) return 0; } return 1; } main() { //file("B"); ios; //cin >> n; scanf("%d", &n); v.pb(0); for(int i = 1; i <= n; i++) { //cin >> a[i]; scanf("%d", &a[i]); mn = min(mn, a[i]); sum += a[i]; v.pb(a[i]); } //sort(a + 1, a + n + 1); vector < int > ans; int right = sum - mn; for(int tmp = 1; tmp <= right; tmp++) { sum -= a[0]; v[0] = a[0] = tmp; sum += a[0]; //cout << sum << endl; if(check()) { ans.pb(tmp); } } printf("%d\n", ans.size()); //cout << ans.size() << endl; for(int i = 0; i < ans.size(); i++) { //cout << ans[i] << " "; printf("%d ", ans[i]); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Correct | 1 ms | 332 KB | Output is correct |
5 | Correct | 18 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 332 KB | Output is correct |
7 | Correct | 1 ms | 332 KB | Output is correct |
8 | Correct | 32 ms | 344 KB | Output is correct |
9 | Correct | 2 ms | 332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Correct | 1 ms | 332 KB | Output is correct |
5 | Correct | 18 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 332 KB | Output is correct |
7 | Correct | 1 ms | 332 KB | Output is correct |
8 | Correct | 32 ms | 344 KB | Output is correct |
9 | Correct | 2 ms | 332 KB | Output is correct |
10 | Correct | 5 ms | 332 KB | Output is correct |
11 | Correct | 8 ms | 332 KB | Output is correct |
12 | Correct | 4 ms | 332 KB | Output is correct |
13 | Correct | 2 ms | 332 KB | Output is correct |
14 | Correct | 13 ms | 336 KB | Output is correct |
15 | Correct | 8 ms | 332 KB | Output is correct |
16 | Correct | 12 ms | 332 KB | Output is correct |
17 | Correct | 3 ms | 332 KB | Output is correct |
18 | Correct | 6 ms | 332 KB | Output is correct |
19 | Correct | 4 ms | 332 KB | Output is correct |
20 | Correct | 5 ms | 332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Correct | 1 ms | 332 KB | Output is correct |
5 | Correct | 18 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 332 KB | Output is correct |
7 | Correct | 1 ms | 332 KB | Output is correct |
8 | Correct | 32 ms | 344 KB | Output is correct |
9 | Correct | 2 ms | 332 KB | Output is correct |
10 | Correct | 5 ms | 332 KB | Output is correct |
11 | Correct | 8 ms | 332 KB | Output is correct |
12 | Correct | 4 ms | 332 KB | Output is correct |
13 | Correct | 2 ms | 332 KB | Output is correct |
14 | Correct | 13 ms | 336 KB | Output is correct |
15 | Correct | 8 ms | 332 KB | Output is correct |
16 | Correct | 12 ms | 332 KB | Output is correct |
17 | Correct | 3 ms | 332 KB | Output is correct |
18 | Correct | 6 ms | 332 KB | Output is correct |
19 | Correct | 4 ms | 332 KB | Output is correct |
20 | Correct | 5 ms | 332 KB | Output is correct |
21 | Execution timed out | 1085 ms | 332 KB | Time limit exceeded |
22 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Correct | 1 ms | 332 KB | Output is correct |
5 | Correct | 18 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 332 KB | Output is correct |
7 | Correct | 1 ms | 332 KB | Output is correct |
8 | Correct | 32 ms | 344 KB | Output is correct |
9 | Correct | 2 ms | 332 KB | Output is correct |
10 | Correct | 5 ms | 332 KB | Output is correct |
11 | Correct | 8 ms | 332 KB | Output is correct |
12 | Correct | 4 ms | 332 KB | Output is correct |
13 | Correct | 2 ms | 332 KB | Output is correct |
14 | Correct | 13 ms | 336 KB | Output is correct |
15 | Correct | 8 ms | 332 KB | Output is correct |
16 | Correct | 12 ms | 332 KB | Output is correct |
17 | Correct | 3 ms | 332 KB | Output is correct |
18 | Correct | 6 ms | 332 KB | Output is correct |
19 | Correct | 4 ms | 332 KB | Output is correct |
20 | Correct | 5 ms | 332 KB | Output is correct |
21 | Execution timed out | 1085 ms | 332 KB | Time limit exceeded |
22 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Correct | 1 ms | 332 KB | Output is correct |
5 | Correct | 18 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 332 KB | Output is correct |
7 | Correct | 1 ms | 332 KB | Output is correct |
8 | Correct | 32 ms | 344 KB | Output is correct |
9 | Correct | 2 ms | 332 KB | Output is correct |
10 | Correct | 5 ms | 332 KB | Output is correct |
11 | Correct | 8 ms | 332 KB | Output is correct |
12 | Correct | 4 ms | 332 KB | Output is correct |
13 | Correct | 2 ms | 332 KB | Output is correct |
14 | Correct | 13 ms | 336 KB | Output is correct |
15 | Correct | 8 ms | 332 KB | Output is correct |
16 | Correct | 12 ms | 332 KB | Output is correct |
17 | Correct | 3 ms | 332 KB | Output is correct |
18 | Correct | 6 ms | 332 KB | Output is correct |
19 | Correct | 4 ms | 332 KB | Output is correct |
20 | Correct | 5 ms | 332 KB | Output is correct |
21 | Execution timed out | 1085 ms | 332 KB | Time limit exceeded |
22 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Correct | 1 ms | 332 KB | Output is correct |
5 | Correct | 18 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 332 KB | Output is correct |
7 | Correct | 1 ms | 332 KB | Output is correct |
8 | Correct | 32 ms | 344 KB | Output is correct |
9 | Correct | 2 ms | 332 KB | Output is correct |
10 | Correct | 5 ms | 332 KB | Output is correct |
11 | Correct | 8 ms | 332 KB | Output is correct |
12 | Correct | 4 ms | 332 KB | Output is correct |
13 | Correct | 2 ms | 332 KB | Output is correct |
14 | Correct | 13 ms | 336 KB | Output is correct |
15 | Correct | 8 ms | 332 KB | Output is correct |
16 | Correct | 12 ms | 332 KB | Output is correct |
17 | Correct | 3 ms | 332 KB | Output is correct |
18 | Correct | 6 ms | 332 KB | Output is correct |
19 | Correct | 4 ms | 332 KB | Output is correct |
20 | Correct | 5 ms | 332 KB | Output is correct |
21 | Execution timed out | 1085 ms | 332 KB | Time limit exceeded |
22 | Halted | 0 ms | 0 KB | - |