QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#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

This is the latest submission verdict.

[2024-08-27 19:11:05]
Judged

Verdict: AC
Time: 298ms
Memory: 6852kb

Show

[2024-08-27 19:11:04]
Submitted

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";
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 3ms

memory: 6716kb

input:

10 5
4 2 7 8 6

output:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

result:

ok single line: '2104'

Test #27:

score: 0

Accepted

time: 2ms

memory: 6776kb

input:

10 4
9 9 9 2

output:

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:

result:

ok single line: '12267'