QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#568667 | #8057. Best Carry Player 4 | stavage | TL | 0ms | 10696kb | C++14 | 2.4kb | 2024-09-16 17:35:13 | 2024-09-16 17:35:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double LD;
//#define int LL
#define double LD
#define endl "\n"
typedef pair<int, int> PII;
const int N = 5e5 + 5;
const int INF = 0x3f3f3f3f;
const double PI = acosl(-1.0);
const double eps = 1e-8;
const int MOD = 1e9 + 7;
int a[N], b[N];
PII p[N];
int m;
bool check(int k, int t)
{
return p[k].second + t >= m;
}
int esum[N];
void solve()
{
scanf("%d", &m);
int suma = 0, sumb = 0;
for (int i = 0; i < m; i++) scanf("%d", &a[i]), suma += a[i];
for (int i = 0; i < m; i++) scanf("%d", &b[i]), sumb += b[i];
if (sumb > suma) swap(a, b);
int n = 0;
for (int i = 0; i < m; i++) {
if (b[i]) p[++n] = {b[i], i};
}
LL ans = 0;
int ca = -1, cb = -1, ssum = INF;
for (int i = 1; i < m; i++) {
if (!a[i]) continue;
int l = 1, r = n, tmp = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid, i)) {
r = mid - 1;
tmp = mid;
}
else {
l = mid + 1;
}
}
if (tmp == -1) continue;
if (ssum > i + p[tmp].second) {
ca = i;
cb = p[tmp].second;
ssum = i + p[tmp].second;
}
}
if (ssum == INF) {
printf("0\n");
return;
}
if (ca != -1 && cb != -1) {
// cout << ca << " " << cb << " " << endl;
a[ca]--;
b[cb]--;
ans++;
}
else {
printf("0\n");
return;
}
// for (int i = 0; i < m; i++) cout << a[i] << endl;
int cnt = 0;
for (int i = m - 1; i >= 0; i--) {
esum[i] = b[i] + esum[i + 1];
}
// for (int i = 0; i < m; i++) cout << esum[i] << " ";
for (int i = 0; i < m; i++) {
if (a[i] >= esum[max(m - i - 1, 0)] - cnt) {
ans += esum[max(m - i - 1, 0)] - cnt;
a[i] -= esum[max(m - i - 1, 0)] - cnt;
cnt = esum[max(m - i - 1, 0)];
}
else {
ans += a[i];
cnt += a[i];
a[i] = 0;
}
}
ans += a[m - 1];
// cout << "olahfc\n";
printf("%lld\n", ans);
}
signed main()
{
// ios::sync_with_stdio(false), cin.tie(0);
int _;
scanf("%d", &_);
// _ = 1;
while (_--) {
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 10696kb
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
Time Limit Exceeded
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 3 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 3 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 ...