QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#184344#6794. Sequence to Sequenceucup-team004#WA 103ms6036kbC++202.1kb2023-09-20 17:24:332023-09-20 17:24:34

Judging History

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

  • [2023-09-20 17:24:34]
  • 评测
  • 测评结果:WA
  • 用时:103ms
  • 内存:6036kb
  • [2023-09-20 17:24:33]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    int n;
    std::cin >> n;
    
    std::vector<int> s(n), t(n);
    for (int i = 0; i < n; i++) {
        std::cin >> s[i];
    }
    for (int i = 0; i < n; i++) {
        std::cin >> t[i];
    }
    
    for (int i = 0; i < n; i++) {
        if (s[i] == 0 && t[i] != 0) {
            std::cout << -1 << "\n";
            return;
        }
    }
    
    std::vector<int> d(n + 1);
    for (int i = 0, j = -1; i <= n; i++) {
        if (i == n || t[i] != 0) {
            int v = (i == n ? 0 : t[i] - s[i]);
            int u = (j == -1 ? 0 : t[j] - s[j]);
            if (v > u) {
                d[i] += v - u;
            } else {
                d[j + 1] += v - u;
            }
            j = i;
        }
    }
    i64 ans = 0;
    for (int i = 0; i <= n; i++) {
        ans += std::abs(d[i]);
    }
    ans /= 2;
    
    std::vector<i64> pre(n), suf(n);
    for (int i = 0; i < n; i++) {
        pre[i] = (i ? pre[i - 1] : 0) + std::min(d[i], 0);
    }
    for (int i = n - 1; i >= 0; i--) {
        suf[i] = (i < n - 1 ? suf[i + 1] : 0) + std::max(d[i + 1], 0);
    }
    
    std::vector<int> a, b;
    for (int i = 0, j = -1; i <= n; i++) {
        if (i == n || t[i] != 0) {
            if (j + 1 < i) {
                int maxs = 0;
                for (int x = j + 1; x < i; x++) {
                    maxs = std::max(maxs, s[x]);
                }
                assert(pre[j + 1] == pre[i - 1]);
                assert(suf[j + 1] == suf[i - 1]);
                a.push_back(std::max(0LL, maxs + pre[j + 1]));
                b.push_back(std::max(0LL, maxs - suf[i - 1]));
            }
            j = i;
        }
    }
    n = a.size();
    int max = 0;
    int res = 0;
    for (int i = 0; i < n; i++) {
        res = std::max(res, max + b[i]);
        max = std::max(max, a[i]);
    }
    ans += res;
    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3512kb

input:

2
5
1 1 1 1 1
2 0 2 0 2
7
3 1 2 3 2 1 4
2 0 0 0 0 0 2

output:

3
3

result:

ok 2 tokens

Test #2:

score: -100
Wrong Answer
time: 103ms
memory: 6036kb

input:

110121
5
0 0 0 0 0
1 4 5 4 1
5
1 0 0 0 0
0 6 8 6 1
5
2 0 0 0 0
4 4 1 3 6
5
3 0 0 0 0
5 1 1 7 6
5
4 0 0 0 0
6 8 7 0 8
5
5 0 0 0 0
5 9 7 7 5
5
6 0 0 0 0
9 2 2 8 0
5
7 0 0 0 0
9 4 7 0 9
5
8 0 0 0 0
6 7 3 7 5
5
9 0 0 0 0
4 0 9 1 4
5
0 1 0 0 0
0 6 6 3 0
5
1 1 0 0 0
3 4 3 4 9
5
2 1 0 0 0
0 4 0 1 4
5
3 1 0...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

wrong answer 2292nd words differ - expected: '17', found: '15'