QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#771425 | #8057. Best Carry Player 4 | Tomorrow# | WA | 76ms | 13912kb | C++17 | 3.1kb | 2024-11-22 12:49:47 | 2024-11-22 12:49:47 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
i64 m, res;
i64 a[500005];
i64 b[500005];
i64 a1[500005];
i64 b1[500005];
i64 hza[500005];
i64 hzb[500005];
void solve(){
cin >> m;
i64 s1 = 0, s2 = 0;
for(int i = 0; i < m; i++){
cin >> a[i];
a1[i] = a[i];
s1 += a[i];
}
for(int i = 0; i < m; i++){
cin >> b[i];
b1[i] = b[i];
s2 += b[i];
}
hza[m] = 0;
hzb[m] = 0;
for(int i = m - 1; i >= 0; i--){
hza[i] = hza[i+1] + a[i];
hzb[i] = hzb[i+1] + b[i];
}
/*
for(int i = 0; i < m; i++){
cout << hza[i] << ' ';
}
cout << endl;
for(int i = 0; i < m; i++){
cout << hzb[i] << ' ';
}
cout << endl;
*/
res = 0;
i64 flag = 1;
i64 l = 0;
i64 flag2 = 0;
for(int i = 1; i < m; i++){
if(b[i] <= 0){
continue;
}
if(hza[m - i] >= 0){
flag2 = 1;
}
}
for(int i = 1; i < m; i++){
if(a[i] <= 0){
continue;
}
if(hzb[m - i] >= 0){
flag2 = 1;
}
}
if(flag2 == 0){
cout << 0 << endl;
return;
}
//res += b1[m-1];
//b1[m-1] = 0;
if(s1 > s2){
i64 c = s1 - s2;
res += min(c, a1[m-1]);
a1[m-1] -= min(c, a1[m-1]);
}
else{
i64 c = s2 - s1;
res += min(c, b1[m-1]);
b1[m-1] -= min(c, b1[m-1]);
}
for(i64 i = m - 1; i >= 0; i--){
while(l < m){
if(l < (m - 1 - i)){
l++;
continue;
}
if(b1[l] < a1[i]){
if(l + i >= m && a1[i] > 0 && b1[l] > 0){
flag = 0;
}
a1[i] -= b1[l];
res += b1[l];
b1[l] = 0;
l++;
continue;
}
if(l + i >= m && a1[i] > 0 && b1[l] > 0){
flag = 0;
}
b1[l] -= a1[i];
res += a1[i];
a1[i] = 0;
break;
}
}
/*
for(int i = 0; i < m; i++){
cout << a1[i] << ' ';
}
cout << endl;
for(int i = 0; i < m; i++){
cout << b1[i] << ' ';
}
cout << endl;
*/
for(int i = 1; i < m; i++){
if(b1[i] <= 0){
continue;
}
if(hza[m - i] >= 0){
flag = 0;
}
}
for(int i = 1; i < m; i++){
if(a1[i] <= 0){
continue;
}
if(hzb[m - i] >= 0){
flag = 0;
}
}
//cout << res << endl;
//cout << flag << endl;
res -= flag;
res = max(0ll, res);
cout << res << endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
if(fopen("test.in","r"))
{
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
}
i64 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: 13852kb
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: 76ms
memory: 13912kb
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 4 0 3 3 3 2 0 0 1 1 3 1 3 1 1 0 0 0 1 1 4 1 4 1 0 2 3 3 1 5 1 0 2 1 1 1 1 0 1 3 5 3 2 2 2 0 1 2 3 2 0 3 1 2 1 1 0 1 0 4 2 2 2 2 0 3 3 0 2 0 1 0 1 2 1 2 1 3 4 0 2 5 0 2 1 1 1 0 3 2 3 0 2 1 4 3 3 1 2 2 2 1 3 1 1 0 1 0 1 0 3 2 2 0 2 1 1 1 2 0 1 2 4 1 3 3 2 2 2 0 2 0 1 2 3 1 3 1 0 3 2 3 0 1 2 1 1 1 ...
result:
wrong answer 14th numbers differ - expected: '0', found: '1'