QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#184344 | #6794. Sequence to Sequence | ucup-team004# | WA | 103ms | 6036kb | C++20 | 2.1kb | 2023-09-20 17:24:33 | 2023-09-20 17:24:34 |
Judging History
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'