QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#376263 | #8057. Best Carry Player 4 | jxu | WA | 94ms | 3828kb | C++17 | 2.6kb | 2024-04-04 00:41:45 | 2024-04-04 00:41:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vld;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<bool> vb;
typedef tuple<int,int,int> ti;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vi> vii;
typedef vector<vii> viii;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T>>;
#define rep(i, a, b) for (int i=a; i<(b); i++)
#define FOR(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(x,A) for (auto& x : A)
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define ins insert
const int MOD = 1000000007;
const char nl = '\n';
ll help(vl A, vl B) {
int m = sz(A);
int j = 0;
ll mismatch = 0;
ll match = 0;
FORd(i, 0, m) {
ll a = A[i];
// I am 9, I want to match with 0
while(j < m && i + j + 1 < m) j++;
while(a && j < m) {
ll b = B[j];
ll cap = min(a, b);
// cout << cap << " matches " << i << " " << j << nl;
match += cap;
a -= cap;
B[j] -= cap;
if (i + j >= m && cap > 0) mismatch++;
if (B[j] == 0) j++;
}
}
// cout << nl;
if (match == 0) return 0;
if (mismatch == 0) match--;
return match;
}
int solve(int tt) {
int m; cin >> m;
vl A(m), B(m);
trav(x, A) cin >> x;
trav(x, B) cin >> x;
ll x = accumulate(all(A), 0);
ll y = accumulate(all(B), 0);
int mx_a = 0;
int mx_b = 0;
rep(i, 0, m) {
if (A[i]) mx_a = i;
if (B[i]) mx_b = i;
}
if (mx_a + mx_b < m) {
cout << 0 << nl;
return 0;
}
if (x < y) {
A[0] += y - x;
} else {
B[0] += x - y;
}
ll ans = max(help(A, B), help(B, A));
cout << ans << nl;
tt++;
return 0;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int T = 1;
cin >> T;
for (int i = 1; i <= T; i++) {
if (solve(i)) break;
}
T++;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3580kb
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: 0
Accepted
time: 52ms
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 0 4 0 3 3 3 2 0 0 1 1 3 0 3 0 0 0 0 0 0 0 4 0 4 1 0 2 3 3 1 5 0 0 2 0 0 1 1 0 0 3 5 3 2 2 2 0 1 2 2 2 0 3 0 2 1 1 0 1 0 4 0 0 2 2 0 3 3 0 2 0 1 0 0 1 1 2 0 3 4 0 2 5 0 2 1 0 0 0 3 2 3 0 2 0 4 3 3 0 2 2 0 1 3 1 1 0 0 0 1 0 3 2 2 0 2 1 1 0 1 0 0 2 4 1 3 3 2 2 2 0 2 0 0 2 3 1 3 1 0 2 2 3 0 1 2 0 1 1 ...
result:
ok 100000 numbers
Test #3:
score: 0
Accepted
time: 29ms
memory: 3576kb
input:
1000 500 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
0 1 1 2 2 2 0 0 0 3 1 1 2 0 1 0 1 1 3 0 0 4 3 1 4 4 0 0 2 1 3 3 0 0 1 0 1 1 0 0 2 1 2 0 3 1 3 1 3 4 2 1 1 2 3 0 0 1 2 0 0 1 1 1 1 2 1 2 2 0 2 2 1 1 3 0 0 1 2 0 1 3 0 0 1 1 0 0 1 0 3 1 2 0 0 5 1 1 1 3 1 4 1 0 0 0 0 0 1 3 1 2 1 0 0 0 0 0 1 1 0 4 0 1 1 3 0 1 0 0 2 3 0 1 2 1 1 1 0 3 0 0 3 2 1 1 0 1 0 1 ...
result:
ok 1000 numbers
Test #4:
score: -100
Wrong Answer
time: 94ms
memory: 3556kb
input:
100000 5 119777838 337555280 806504015 458289944 321614229 979242871 431783189 423329635 193632121 7339369 5 189264782 667669243 753322761 861814678 224007583 977519325 104432095 940220826 712094722 903574615 5 977791540 278658984 601762324 633391706 36807634 689562032 997406456 118939957 891425821 ...
output:
1377698543 2884329841 1699584169 1780759937 2531472710 2754014935 1950741996 2577893498 1671531479 1655223784 1476887044 2115933812 1332546839 958870781 600795101 927483202 2136597299 1883468626 2291627593 1436067851 2412405837 1884010446 1960543235 2014856631 848686688 1069641213 2133866856 1597069...
result:
wrong answer 4th numbers differ - expected: '2132012702', found: '1780759937'