QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#349503 | #8057. Best Carry Player 4 | pipoika# | WA | 139ms | 3828kb | C++17 | 1.9kb | 2024-03-10 02:28:42 | 2024-03-10 02:28:42 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<(k);++i)
#define all(i) (i).begin(),(i).end()
#define sz(i) (int)(i).size()
using namespace std;
typedef long long ll;
typedef vector<int> vi;
vi first, second, links;
int next(int i) {
if (links[i] == i) return i;
return links[i] = next(links[i]);
}
int main() {
int t;
cin >> t;
while (t--) {
int m;
cin >> m;
first.resize(m);
second.resize(m);
links.resize(m+1);
iota(all(links), 0);
ll diff = 0;
rep(i,0,m) {
cin >> first[i];
diff += first[i];
}
rep(i,0,m) {
cin >> second[i];
diff -= second[i];
}
if (diff < 0) first[0] += 1000000000;
else second[0] += 1000000000;
ll ans = 0;
int dec=1;
rep(i,0,m) {
int cur = first[i];
int it = m-1-i;
it=next(it);
while (cur && it<m) {
if (it > m-1-i) dec=0;
int sub = min(cur, second[it]);
// cout << cur << ' ' << second[it] << ' ' << sub << endl;
ans += sub;
cur -= sub;
second[it] -= sub;
if (second[it] <= 0) {
links[it] = it+1;
it=next(it);
}
else break;
}
}
rep(i,0,m) if (first[i]) {
int it = m-i; // 1 bigger
it=next(it);
// cout << i << ' ' << it << ' '<< first[i] << ' '<< second[it] << endl;
if (it < m) { // could have used one bigger
dec=0;
break;
}
}
ans-=dec;
printf("%lld\n",ans);
// break;
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3744kb
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: 139ms
memory: 3828kb
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 -1 4 -1 3 4 3 2 -1 -1 1 1 3 0 3 1 1 0 -1 0 1 0 4 1 4 2 -1 2 3 3 1 5 0 -1 2 0 1 1 1 -1 1 3 5 3 2 2 1 -1 0 2 3 2 0 3 1 2 1 1 1 1 -1 4 2 2 2 2 0 3 3 -1 2 -1 2 -1 1 2 1 2 0 3 4 -1 2 5 -1 2 1 1 1 -1 3 2 4 -1 2 0 4 3 3 0 2 2 1 1 3 1 1 -1 1 -1 1 -1 3 2 2 0 2 1 1 0 1 -1 1 3 4 1 3 3 2 2 2 -1 2 0 0 2 3 1 3 ...
result:
wrong answer 2nd numbers differ - expected: '0', found: '-1'