QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#867765	#2726. Fun Palace	hhoppitree	25 ✓	26ms	82464kb	C++17	1.0kb	2025-01-23 23:32:01	2025-01-23 23:32:03

Judging History

This is the latest submission verdict.

[2025-01-23 23:32:03]
Judged

Verdict: 25
Time: 26ms
Memory: 82464kb

Show

[2025-01-23 23:32:01]
Submitted

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 1005;

int f[N][20005], a[N], b[N];

signed main() {
    int n, m; scanf("%d%d", &n, &m);
    for (int i = 1; i < n; ++i) {
        scanf("%d%d", &a[i], &b[i]);
    }
    memset(f, -0x3f, sizeof(f));
    for (int i = 0; i < m; ++i) f[1][i] = i;
    for (int i = 1; i < n; ++i) {
        int tmp = -2e9;
        for (int j = 0; j <= 20000; ++j) {
            if (f[i][j] < 0) continue;
            if (j < a[i]) {
                tmp = max(tmp, f[i][j]);
                f[i + 1][j + b[i]] = max(f[i + 1][j + b[i]], f[i][j] + b[i]);
            } else if (j < a[i] + b[i]) {
                f[i + 1][j - a[i]] = max(f[i + 1][j - a[i]], f[i][j]);
            } else {
                f[i + 1][j] = max(f[i + 1][j], f[i][j]);
            }
        }
        for (int j = 0; j < b[i]; ++j) {
            f[i + 1][j] = max(f[i + 1][j], tmp + j);
        }
    }
    printf("%d\n", *max_element(f[n], f[n] + 20000 + 1));
    return 0;
}

源文件, 语言: C++17

詳細信息

Subtask #1:

score: 3

Accepted

Test #1:

score: 3

Accepted

time: 4ms

memory: 82440kb

input:

2
1
1 1

output:

result:

ok single line: '1'

Test #2:

score: 3

Accepted

time: 1ms

memory: 82356kb

input:

output:

result:

ok single line: '1'

Test #3:

score: 3

Accepted

time: 2ms

memory: 82404kb

input:

output:

result:

ok single line: '2'

Test #4:

score: 3

Accepted

time: 2ms

memory: 82464kb

input:

output:

result:

ok single line: '3'

Test #5:

score: 3

Accepted

time: 4ms

memory: 82452kb

input:

output:

result:

ok single line: '3'

Test #6:

score: 3

Accepted

time: 2ms

memory: 82376kb

input:

output:

result:

ok single line: '8'

Subtask #2:

score: 5

Accepted

Test #7:

score: 5

Accepted

time: 0ms

memory: 82188kb

input:

1
1

output:

result:

ok single line: '0'

Test #8:

score: 5

Accepted

time: 1ms

memory: 82432kb

input:

1
2

output:

result:

ok single line: '1'

Test #9:

score: 5

Accepted

time: 8ms

memory: 82392kb

input:

output:

result:

ok single line: '717'

Test #10:

score: 5

Accepted

time: 12ms

memory: 82376kb

input:

output:

result:

ok single line: '707'

Subtask #3:

score: 12

Accepted

Test #11:

score: 12

Accepted

time: 1ms

memory: 82444kb

input:

2
20
5 5

output:

result:

ok single line: '19'

Test #12:

score: 12

Accepted

time: 3ms

memory: 82364kb

input:

2
20
5 20

output:

result:

ok single line: '24'

Test #13:

score: 12

Accepted

time: 5ms

memory: 82352kb

input:

output:

result:

ok single line: '23'

Test #14:

score: 12

Accepted

time: 5ms

memory: 82372kb

input:

1
122

output:

result:

ok single line: '121'

Test #15:

score: 12

Accepted

time: 4ms

memory: 82316kb

input:

1
11

output:

result:

ok single line: '10'

Test #16:

score: 12

Accepted

time: 6ms

memory: 82392kb

input:

output:

result:

ok single line: '14013'

Test #17:

score: 12

Accepted

time: 1ms

memory: 82344kb

input:

output:

result:

ok single line: '14097'

Subtask #4:

score: 5

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Test #18:

score: 5

Accepted

time: 13ms

memory: 82260kb

input:

output:

result:

ok single line: '500'

Test #19:

score: 5

Accepted

time: 10ms

memory: 82336kb

input:

output:

result:

ok single line: '491'

Test #20:

score: 5

Accepted

time: 2ms

memory: 82324kb

input:

1
8655

output:

result:

ok single line: '8654'

Test #21:

score: 5

Accepted

time: 25ms

memory: 82304kb

input:

output:

result:

ok single line: '3503312'

Test #22:

score: 5

Accepted

time: 26ms

memory: 82364kb

input:

1000
4618
1834 6250
6621 4954
2412 8894
2109 8198
4405 862
7385 9786
1492 1938
7371 9595
1870 1079
5424 9503
4520 8990
4233 7775
9952 4747
301 4268
8197 5382
3270 424
3114 3294
8559 3320
6311 9345
13 2921
5912 9444
1667 6056
220 8529
3852 168
8455 2740
5109 10000
896 302
1295 9547
7668 8131
9250 674...

output:

result:

ok single line: '3505300'

Test #23:

score: 5

Accepted

time: 24ms

memory: 82428kb

input:

output:

result:

ok single line: '3413376'

Test #24:

score: 5

Accepted

time: 19ms

memory: 82448kb

input:

output:

result:

ok single line: '2426822'

Extra Test:

score: 0

Extra Test Passed