QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#680715 | #8057. Best Carry Player 4 | FangYifan | WA | 42ms | 3804kb | C++17 | 1.8kb | 2024-10-26 22:17:28 | 2024-10-26 22:17:28 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
constexpr int mod = 998244353;
constexpr int N = 1e6 + 10;
void solve() {
int n;
cin >> n;
ll suma = 0, sumb = 0;
vector<ll> a(n), b(n);
for (int i = 0; i < n; i++) cin >> a[i], suma += a[i];
for (int i = 0; i < n; i++) cin >> b[i], sumb += b[i];
if (suma > sumb) b[0] += suma - sumb;
else a[0] += sumb - suma;
ll match1 = 0;
int cnt = 0, maxa1 = 0, maxb1 = 0;
for (int i = 0; i < n; i++) {
ll k = min(a[i], b[n - 1 - i]);
if (k > 0) {
cnt++;
match1 += k;
a[i] -= k;
b[n - 1 - i] -= k;
maxa1 = max(maxa1, i);
maxb1 = max(maxb1, n - 1 - i);
}
}
ll match2 = 0;
for (int i = 0, j = 0; j < n; j++) {
if (b[n - 1 - j] == 0) continue;
while (i <= j) i++;
while (i < n && a[i] <= b[n - 1 - j]) {
a[i] = 0;
b[n - 1 - j] -= a[i];
match2 += a[i];
i++;
}
if (i < n && a[i] > b[n - 1 - j]) {
match2 += b[n - 1 - j];
a[i] -= b[n - 1 - j];
b[n - 1 - j] = 0;
}
}
if (match2) {
cout << match1 + match2 << "\n";
return;
}
int maxa2 = 0, maxb2 = 0;
for (int i = 0; i < n; i++) if (a[i]) maxa2 = i;
for (int i = 0; i < n; i++) if (b[i]) maxb2 = i;
if (maxa1 + maxb2 >= n || maxa2 + maxb1 >= n) {
cout << match1 << "\n";
return;
}
if (cnt >= 2) {
cout << match1 - 1 << "\n";
return;
}
cout << "0\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt = 1;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3804kb
input:
5 2 1 2 3 4 3 1 0 1 0 1 0 4 1 0 0 1 1 1 1 1 5 123456 114514 1919810 233333 234567 20050815 998244353 0 0 0 10 5 3 5 3 2 4 2 4 1 5 9 9 8 2 4 4 3 5 3 0
output:
5 1 2 467900 29
result:
ok 5 number(s): "5 1 2 467900 29"
Test #2:
score: -100
Wrong Answer
time: 42ms
memory: 3592kb
input:
100000 5 0 1 1 1 1 0 0 1 0 0 5 0 0 0 0 0 1 1 1 0 0 5 0 0 2 1 1 0 2 1 0 1 5 0 0 0 0 0 1 2 1 0 0 5 0 1 0 1 1 0 0 1 1 1 5 2 0 0 0 1 1 0 0 0 3 5 2 0 0 1 1 0 2 1 1 1 5 0 0 0 0 2 0 0 0 0 1 5 0 0 0 0 0 0 1 1 0 0 5 4 0 0 0 0 0 0 0 1 0 5 0 0 0 0 1 2 1 1 0 0 5 0 2 3 0 0 0 0 0 1 0 5 1 1 1 0 1 1 0 1 0 1 5 0 0 0...
output:
2 0 2 0 1 3 2 1 0 0 1 1 3 0 2 0 0 0 0 0 0 0 3 0 4 1 0 1 1 2 1 3 0 0 2 0 0 0 0 0 0 2 4 2 2 0 2 0 1 2 2 2 0 0 0 1 1 1 0 0 0 4 0 0 0 2 0 2 0 0 1 0 1 0 0 1 1 2 0 1 4 0 2 1 0 2 1 0 0 0 3 2 3 0 2 0 4 3 3 0 2 1 0 1 2 1 1 0 0 0 0 0 2 0 0 0 2 1 0 0 1 0 0 2 2 1 3 2 2 2 0 0 2 0 0 1 3 1 3 1 0 2 0 2 0 1 2 0 1 1 ...
result:
wrong answer 3rd numbers differ - expected: '4', found: '2'