QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#706567#4591. Maxdifficent Grouparnold518#WA 7ms7160kbC++171001b2024-11-03 12:17:302024-11-03 12:17:30

Judging History

你现在查看的是最新测评结果

  • [2024-11-03 12:17:30]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:7160kb
  • [2024-11-03 12:17:30]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long long lint;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

lint N;
vector<lint> a;

lint solve(vector<lint> v) {
    lint N = v.size();

    vector<lint> sum = {v[0]}, pfx, sfx;

    for (int i=1; i<N; i++) sum.push_back(sum[i-1] + v[i]);

    pfx.resize(N);
    sfx.resize(N);

    pfx[0] = sum[0];
    for (int i=1; i<N; i++) pfx[i] = max(pfx[i-1], sum[i]);

    sfx[N-1] = sum[N-1];
    for (int i=N-2; i>=0; i--) sfx[i] = max(sfx[i+1], sum[i]);

    lint ans = 0;
    for (int k=0; k+1<N; k++) {
        lint now = -2 * sum[k];

        if (k > 0) now += pfx[k-1];
        now += sfx[k+1];

        ans = max(ans, now);
    }

    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    cin >> N;

    a.resize(N);
    for (int i=0; i<N; i++) cin >> a[i];

    lint ans = solve(a);

    reverse(a.begin(), a.end());

    ans = max(ans, solve(a));

    cout << ans << '\n';
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3636kb

input:

4
100 -30 -20 50

output:

150

result:

ok single line: '150'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

5
12 7 4 32 9

output:

46

result:

ok single line: '46'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

6
-5 10 -5 45 -20 15

output:

70

result:

ok single line: '70'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

14
1 5 3 4 2 -4 -2 -6 -5 6 4 2 3 9

output:

41

result:

ok single line: '41'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

2
0 -900000

output:

900000

result:

ok single line: '900000'

Test #6:

score: 0
Accepted
time: 2ms
memory: 5628kb

input:

59394
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 0 ...

output:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 2ms
memory: 5940kb

input:

63744
-1 0 1 1 0 0 1 -1 -1 -1 -1 -1 1 1 1 -1 0 0 1 1 1 -1 1 -1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 0 1 0 1 -1 1 1 1 -1 1 -1 0 0 -1 -1 1 1 0 0 0 1 0 -1 -1 0 0 0 1 -1 0 1 0 0 1 -1 -1 0 0 -1 -1 1 0 1 0 1 0 -1 0 -1 1 1 -1 1 1 -1 1 -1 1 0 0 -1 1 1 0 0 -1 0 0 1 0 0 1 -1 1 0 1 0 -1 0 0 1 0 0 -1 0 0 0 -1 0 0 1 -1 -...

output:

475

result:

ok single line: '475'

Test #8:

score: 0
Accepted
time: 7ms
memory: 7160kb

input:

87255
4 -9 3 -3 -2 -2 3 10 -7 -10 -5 5 -9 -7 1 -1 10 0 -1 1 10 -9 -8 8 5 -8 2 -3 -7 7 -5 -3 3 -2 5 -1 -5 6 -2 8 3 0 -6 5 -10 5 0 -8 -3 -1 -7 -3 0 7 -4 5 -1 -5 -9 -2 8 7 6 -2 6 9 -2 6 10 3 10 -10 4 5 -9 0 -10 -9 -10 6 9 -5 -3 -7 -2 -4 6 4 7 -4 4 2 -8 -2 -4 3 2 -9 -4 9 3 8 -5 -1 8 -10 8 -3 -6 7 -1 8 -...

output:

5780

result:

ok single line: '5780'

Test #9:

score: 0
Accepted
time: 0ms
memory: 4204kb

input:

22859
123270 568778 416102 510776 597790 125263 860375 89550 16897 909046 124583 592535 32050 175429 993750 899188 863104 608753 724971 728319 82786 733737 923128 266621 57189 518044 556356 756193 408537 94718 998619 206034 125763 649241 204930 474150 57466 358193 153011 416494 753281 480726 927554 ...

output:

11402652338

result:

ok single line: '11402652338'

Test #10:

score: -100
Wrong Answer
time: 3ms
memory: 4824kb

input:

33834
-514303 -172893 -206523 -8184 -343624 -208669 -690452 -17023 -342571 -830835 -999032 -533750 -822347 -62447 -85968 -172653 -485779 -40414 -37219 -564266 -427415 -565431 -197676 -911379 -238653 -602443 -410483 -122721 -921143 -764784 -355380 -23053 -510189 -547702 -165836 -672416 -12018 -966618...

output:

16850956029

result:

wrong answer 1st lines differ - expected: '16851470332', found: '16850956029'