QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #535073 | #5590. Exponent Exchange | stasio6 | AC ✓ | 298ms | 6852kb | C++14 | 2.1kb | 2024-08-27 19:11:04 | 2024-08-27 19:11:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll
#define rep(i,a,b) for(int i = a; i < (b); i++)
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define PB push_back
#define FS first
#define SD second
template<class X, class Y> void cmn(X &a, Y b) { a=min<X>(a, b); }
template<class X, class Y> void cmx(X &a, Y b) { a=max<X>(a, b); }
typedef pair<int, int> pii;
typedef vector<int> vi;
int dp[2][200002][2];
int cyf[1002];
signed main() {
cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
int b, p;
cin >> b >> p;
for (int i = p-1; i >= 0; i--) {
cin >> cyf[i];
}
for (int i = 0; i <= 1; i++) {
for (int j = 0; j <= 200000; j++) {
dp[i][j][0] = dp[i][j][1] = 1000000001;
}
}
dp[0][100000][0] = 0;
for (int i = 0; i < p; i++) {
int pi = i%2, npi = 1 - pi;
for (int j = 0; j <= 200000; j++) {
dp[npi][j][0] = dp[npi][j][1] = 1000000001;
}
for (int j = 0; j <= 200000; j++) {
int diff = j - 100000;
for (int k = 0; k < 2; k++) {
if (dp[pi][j][k] >= 1000000000)
continue;
// cerr << i << " " << diff << " " << k << " " << dp[i][j][k] << "\n";
int mojcyf = (cyf[i] + k), jejcyf = (b - mojcyf);
// cerr << mojcyf << " " << jejcyf << "\n";
if (j + mojcyf >= 0 && j + mojcyf <= 200000)
cmn(dp[npi][j+mojcyf][0], dp[pi][j][k] + mojcyf);
if (j - jejcyf >= 0 && j - jejcyf <= 200000)
cmn(dp[npi][j-jejcyf][1], dp[pi][j][k] + jejcyf);
}
}
}
int best = 1000000000;
for (int j = 0; j <= 200000; j++) {
for (int k = 0; k < 2; k++) {
int diff = j - 100000;
// if (dp[p][j][k] < 10)
// cerr << diff << " " << k << " " << dp[p][j][k] << "\n";
cmn(best, (dp[p%2][j][k] + abs(diff))/2);
}
}
cout << best << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 6716kb
input:
10 5 4 2 7 8 6
output:
7
result:
ok single line: '7'
Test #2:
score: 0
Accepted
time: 30ms
memory: 6720kb
input:
2 100 1 1 1 1 0 0 1 1 1 0 1 1 1 0 0 1 0 0 1 0 0 1 1 1 0 1 1 0 1 1 1 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 0 0 1 0 1 0 1 0 0 1 1 0 0 0 0 1 0 1 1 1 1 0 1 1 0 1 1 0 0 0 0 1 1 1
output:
19
result:
ok single line: '19'
Test #3:
score: 0
Accepted
time: 31ms
memory: 6836kb
input:
2 100 1 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 1 0 1 0 1 0 1 0 0 1 0 0 1 0 1 0 0 1 0 1 0 0 0 1 0 1 1 0 1 1 1 0 0 0 0 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 1 0 0 1 0 0
output:
20
result:
ok single line: '20'
Test #4:
score: 0
Accepted
time: 298ms
memory: 6832kb
input:
100 1000 27 21 72 90 53 34 19 36 54 48 74 65 73 50 86 92 85 84 1 57 16 40 16 97 39 62 8 11 31 4 29 56 54 29 59 22 84 65 91 25 94 96 20 30 55 62 17 19 15 40 79 75 2 74 37 53 94 69 57 21 21 39 71 2 50 12 72 98 18 84 38 81 81 11 6 69 49 52 47 25 86 10 72 74 29 16 99 28 8 9 95 62 39 25 3 20 35 20 72 82 ...
output:
12638
result:
ok single line: '12638'
Test #5:
score: 0
Accepted
time: 31ms
memory: 6752kb
input:
2 100 1 1 1 1 0 1 1 1 1 0 0 1 0 1 1 0 0 0 0 1 0 0 0 1 1 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 1 0 1 0 1 1 1 0 0 1 0 1 0 1 0 1 0 1
output:
21
result:
ok single line: '21'
Test #6:
score: 0
Accepted
time: 101ms
memory: 6728kb
input:
60 336 41 4 6 27 26 6 16 48 30 53 18 29 57 19 1 52 42 50 34 21 40 43 18 44 56 22 22 16 32 59 17 59 6 31 15 18 39 21 23 12 20 3 26 32 7 30 26 43 44 16 48 21 17 20 12 33 4 52 39 24 44 50 36 34 23 10 13 23 31 50 49 11 53 56 46 36 47 30 59 0 0 4 0 11 25 12 53 42 49 35 14 16 27 28 56 44 48 17 57 2 37 38 ...
output:
2490
result:
ok single line: '2490'
Test #7:
score: 0
Accepted
time: 88ms
memory: 6780kb
input:
17 302 15 16 1 13 9 15 7 11 3 15 15 3 3 16 4 14 13 11 0 15 14 0 6 3 13 5 11 5 15 1 3 0 15 13 15 4 9 11 1 16 4 3 8 8 9 13 10 5 16 10 16 15 12 14 11 12 7 3 6 1 5 4 3 12 6 9 6 12 1 11 10 8 7 0 11 8 12 15 11 7 10 12 11 0 11 13 9 7 10 14 6 15 1 12 12 4 9 5 12 2 2 5 8 6 6 0 6 10 4 16 3 15 5 9 12 1 2 5 13 ...
output:
673
result:
ok single line: '673'
Test #8:
score: 0
Accepted
time: 174ms
memory: 6716kb
input:
11 608 5 10 0 10 2 9 9 6 0 5 0 4 10 2 9 5 7 10 2 6 7 10 7 5 1 4 1 0 3 1 9 7 4 3 5 6 0 6 9 10 9 5 3 4 6 7 10 1 0 5 3 10 10 0 7 3 5 3 1 2 9 5 10 5 7 4 7 5 1 0 6 5 10 2 5 1 5 7 3 10 10 5 0 9 6 0 9 6 10 0 9 0 5 6 8 3 8 4 3 9 7 10 1 10 2 10 1 3 8 2 9 5 1 1 2 9 2 0 10 0 1 7 5 9 3 2 5 1 10 8 8 1 6 2 4 7 9 ...
output:
828
result:
ok single line: '828'
Test #9:
score: 0
Accepted
time: 137ms
memory: 6796kb
input:
89 462 88 62 73 50 60 23 24 81 21 59 53 50 41 46 11 86 76 64 32 42 34 6 81 75 0 43 37 35 33 11 15 84 12 38 43 17 81 11 68 7 16 23 13 27 21 56 71 77 64 55 64 42 71 18 2 17 78 17 58 31 60 29 65 85 34 74 8 74 1 17 77 30 51 50 49 19 5 29 33 88 86 17 28 76 3 39 68 40 77 48 28 2 82 44 85 43 42 0 49 46 29 ...
output:
5298
result:
ok single line: '5298'
Test #10:
score: 0
Accepted
time: 181ms
memory: 6720kb
input:
18 630 1 0 10 9 3 2 13 11 3 14 1 0 5 0 17 3 10 16 16 6 4 13 1 9 7 12 7 4 17 11 5 12 7 0 12 15 9 15 3 14 7 8 15 5 8 9 15 9 3 6 2 17 14 8 8 12 13 15 6 15 14 1 9 14 0 17 4 5 10 7 13 14 0 7 16 9 17 17 4 9 13 3 2 12 2 12 9 6 17 1 14 2 11 15 8 17 8 3 16 12 6 14 10 0 1 8 4 14 9 10 12 3 5 17 12 4 13 10 13 1...
output:
1430
result:
ok single line: '1430'
Test #11:
score: 0
Accepted
time: 99ms
memory: 6804kb
input:
49 354 20 22 42 12 21 21 45 17 29 38 23 21 21 42 26 45 3 45 16 3 10 17 2 21 21 14 21 1 37 6 40 22 26 36 47 8 39 30 39 32 14 19 13 37 1 43 14 26 16 31 8 37 23 29 13 17 6 7 27 24 21 35 37 43 48 41 37 48 15 1 8 21 38 13 46 34 34 0 35 32 0 28 42 36 3 46 40 12 28 33 46 43 10 35 12 18 42 25 26 0 17 8 1 2 ...
output:
2117
result:
ok single line: '2117'
Test #12:
score: 0
Accepted
time: 12ms
memory: 6832kb
input:
30 49 4 0 4 2 26 19 27 25 10 21 12 24 3 29 8 5 29 16 19 5 5 19 17 20 3 14 22 18 29 29 1 7 5 2 26 26 11 21 17 29 5 10 26 3 2 18 17 20 12
output:
164
result:
ok single line: '164'
Test #13:
score: 0
Accepted
time: 144ms
memory: 6836kb
input:
50 494 27 34 10 23 15 6 2 49 32 12 42 4 8 12 6 7 10 1 14 17 33 30 12 37 40 38 37 41 43 8 46 9 38 48 30 4 24 47 17 11 13 1 11 7 15 33 45 33 7 37 37 27 34 12 7 11 7 41 26 6 36 47 44 8 10 5 9 7 14 17 8 17 13 28 29 6 12 29 23 43 32 32 19 44 18 46 30 42 41 43 38 20 48 4 44 30 45 25 16 21 9 45 15 6 28 39 ...
output:
3219
result:
ok single line: '3219'
Test #14:
score: 0
Accepted
time: 38ms
memory: 6848kb
input:
28 137 14 10 21 12 16 18 13 6 19 5 12 10 21 24 25 2 2 14 18 7 8 27 19 8 15 14 27 25 22 11 4 25 20 7 14 15 12 25 10 19 18 1 22 18 8 13 2 9 14 13 26 16 12 17 19 15 10 5 5 19 24 11 16 11 6 0 27 23 1 10 10 19 12 20 12 22 1 23 4 25 24 14 23 18 0 10 19 16 12 10 17 4 14 24 21 0 0 22 16 17 13 10 11 24 6 26 ...
output:
534
result:
ok single line: '534'
Test #15:
score: 0
Accepted
time: 53ms
memory: 6840kb
input:
28 179 9 20 19 27 25 14 17 11 22 3 6 23 10 8 22 12 20 21 26 15 24 19 7 12 10 11 3 9 20 3 17 16 11 1 23 11 21 12 25 18 18 1 13 16 3 11 14 13 10 25 22 4 27 8 5 12 4 18 23 21 6 16 16 2 19 12 6 12 14 27 27 15 3 12 0 16 27 11 1 7 25 13 2 17 10 17 17 5 9 15 19 12 27 3 8 1 7 22 20 7 5 26 15 6 0 18 16 8 2 3...
output:
657
result:
ok single line: '657'
Test #16:
score: 0
Accepted
time: 129ms
memory: 6712kb
input:
6 448 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 ...
output:
360
result:
ok single line: '360'
Test #17:
score: 0
Accepted
time: 61ms
memory: 6792kb
input:
50 206 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
1
result:
ok single line: '1'
Test #18:
score: 0
Accepted
time: 57ms
memory: 6852kb
input:
99 191 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62...
output:
4357
result:
ok single line: '4357'
Test #19:
score: 0
Accepted
time: 242ms
memory: 6780kb
input:
79 828 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43...
output:
15996
result:
ok single line: '15996'
Test #20:
score: 0
Accepted
time: 191ms
memory: 6716kb
input:
41 654 13 13 37 13 13 13 13 37 13 13 37 37 13 37 13 13 37 37 37 37 37 37 13 13 37 37 37 13 37 37 13 13 13 13 13 13 37 37 37 13 37 37 13 37 13 13 13 13 37 37 37 13 13 37 13 13 37 13 37 37 37 13 13 37 37 37 13 13 37 13 13 13 37 13 37 37 37 37 13 37 37 37 13 13 37 13 13 13 37 13 13 13 13 37 13 13 13 13...
output:
3437
result:
ok single line: '3437'
Test #21:
score: 0
Accepted
time: 132ms
memory: 6792kb
input:
77 455 49 59 49 49 59 59 59 59 59 49 59 49 59 49 59 59 49 49 59 49 49 59 49 59 59 49 49 49 49 49 49 59 49 49 49 49 59 49 49 59 49 59 49 49 49 59 49 49 49 59 59 49 49 59 59 49 59 59 59 49 59 49 49 59 59 59 59 49 59 49 59 59 49 49 49 49 49 59 59 59 49 49 49 59 49 49 49 59 49 49 59 49 49 59 59 59 49 49...
output:
6567
result:
ok single line: '6567'
Test #22:
score: 0
Accepted
time: 248ms
memory: 6784kb
input:
18 874 1 14 14 14 14 1 14 1 1 14 1 1 14 1 1 14 1 1 14 14 14 14 14 14 1 1 1 14 1 14 14 14 1 14 14 14 1 14 1 14 1 1 14 1 1 1 1 1 14 1 14 14 14 14 1 14 1 1 14 14 14 1 14 1 1 1 1 14 14 1 14 14 1 1 1 14 1 1 14 1 14 1 14 14 14 1 1 1 1 1 1 14 14 1 1 1 1 1 1 1 14 14 14 1 14 14 14 1 14 14 14 14 1 1 14 14 14 ...
output:
1298
result:
ok single line: '1298'
Test #23:
score: 0
Accepted
time: 239ms
memory: 6776kb
input:
44 821 10 10 10 43 10 10 10 10 10 10 43 43 43 10 43 10 10 43 10 10 10 10 43 43 43 10 43 43 10 10 10 43 10 43 43 43 43 43 10 10 43 10 10 43 10 10 10 10 10 10 10 10 10 10 43 10 10 43 43 43 10 10 43 10 10 10 10 43 43 10 43 43 10 10 43 10 43 10 10 43 10 10 10 43 10 43 10 10 10 10 10 10 43 10 10 10 10 10...
output:
3311
result:
ok single line: '3311'
Test #24:
score: 0
Accepted
time: 15ms
memory: 6780kb
input:
41 47 22 9 22 22 22 9 22 22 9 22 9 9 9 9 9 22 9 22 22 9 9 9 9 9 9 9 9 22 9 9 22 9 22 9 22 9 9 22 22 9 22 9 22 9 9 9 22
output:
318
result:
ok single line: '318'
Test #25:
score: 0
Accepted
time: 161ms
memory: 6720kb
input:
45 552 7 7 7 37 7 7 7 37 37 7 7 37 37 7 37 7 37 37 7 37 37 7 7 7 7 7 7 37 37 37 7 37 7 7 37 37 7 7 37 37 7 37 7 7 37 37 7 37 7 7 7 37 37 7 7 7 7 37 37 7 37 7 37 37 37 37 7 7 37 7 37 37 37 7 37 7 7 37 37 37 37 7 7 37 37 37 37 7 37 7 7 7 37 7 7 7 7 37 37 37 7 37 7 37 37 37 7 37 7 7 7 37 37 37 37 37 7 ...
output:
2085
result:
ok single line: '2085'
Test #26:
score: 0
Accepted
time: 61ms
memory: 6712kb
input:
75 202 43 10 10 10 10 10 10 10 10 43 43 43 10 10 10 10 43 43 43 43 43 43 43 43 43 10 43 43 10 43 43 43 10 43 10 10 43 43 43 10 43 10 10 10 10 10 10 10 43 10 43 43 43 10 10 10 43 43 10 10 10 43 10 10 10 43 10 10 10 10 43 43 43 10 10 10 10 10 10 10 43 10 10 10 10 10 10 43 43 43 10 10 43 10 10 10 43 43...
output:
2104
result:
ok single line: '2104'
Test #27:
score: 0
Accepted
time: 2ms
memory: 6776kb
input:
10 4 9 9 9 2
output:
2
result:
ok single line: '2'
Test #28:
score: 0
Accepted
time: 297ms
memory: 6780kb
input:
100 1000 67 1 90 44 92 70 22 92 37 68 53 9 84 34 52 64 23 95 84 93 38 2 60 1 40 16 46 8 46 80 68 53 20 55 24 58 17 71 22 41 63 64 26 57 88 68 58 16 77 57 28 38 29 11 63 48 7 8 42 49 53 66 64 85 75 18 58 96 80 36 80 42 68 96 13 38 84 93 78 22 31 73 91 82 41 25 65 15 7 95 54 88 89 39 26 65 61 52 83 62...
output:
12267
result:
ok single line: '12267'