QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#385885#8057. Best Carry Player 4WillisWA 45ms3820kbC++203.0kb2024-04-11 09:36:152024-04-11 09:36:15

Judging History

你现在查看的是最新测评结果

  • [2024-04-11 09:36:15]
  • 评测
  • 测评结果:WA
  • 用时:45ms
  • 内存:3820kb
  • [2024-04-11 09:36:15]
  • 提交

answer

#ifdef local
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#endif
// #pragma comment(linker, "/STACK:102400000,102400000")

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#ifndef local
#define endl '\n'
#endif

#define pb emplace_back
#define fi first
#define se second
// #define endl '\n'
#define rep(i, l, r) for (long long i = l; i <= r; i++)
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, x) memset(a, x, sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
typedef pair<int, int> P;
typedef pair<P, int> PP;
const double pi = acos(-1);
typedef __int128_t int128;
const ll mod = 1e18;
const db eps = 1e-9;
std::mt19937_64 rng(time(0));
ll my_random(ll l, ll r)
{

	uniform_int_distribution<int> range(l, r);
	return range(rng);
}
void __()
{
#ifdef local
	system("pause");
#endif
}

ll qp(ll a, ll b, ll mod)
{
	ll ans = 1;
	while (b)
	{
		if (b & 1)
			ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}
const int maxn = 5e5 + 10;

ll a[maxn];
ll b[maxn];
ll suf[maxn];
int n;
signed main()
{
	IOS;

	int t = 1;
	cin >> t;
	while (t--)
	{
		cin >> n;
		for (int i = 0; i < n; i++)
			cin >> a[i];
		for (int i = 0; i < n; i++)
			cin >> b[i];
		for (int i = 0; i <= n; i++)
			suf[i] = 0;
		for (int i = n - 1; i >= 0; i--)
			suf[i] = suf[i + 1] + b[i];
		a[0] = b[0] = 1e15;
		// for (int i = 0; i < n; i++)
		//	cout << suf[i] << " ";
		// cout << endl;
		int mxa = 0;
		for (int i = n - 1; i >= 0; i--)
			if (a[i] > 0)
			{
				mxa = i;
				break;
			}
		bool f = 0;
		for (int i = n - 1; i >= 0; i--)
		{
			if (a[i] == 0)
				continue;
			ll tmp = suf[n - i];
			// cout << i << " " << n - i << " " << suf[n - i] << endl;
			if (tmp != 0)
				f = 1;
			// cout << "XXX " << f << endl;
			if (f)
				break;
		}
		if (!f)
		{
			cout << 0 << endl;
			continue;
		}
		ll ans = 0;
		bool f2 = 0;
		int j = 0;
		for (int i = n - 1; i >= 0; i--)
		{
			while (a[i] > 0)
			{
				ll bns = min(b[j], a[i]);
				ans += bns;
				b[j] -= bns;
				a[i] -= bns;
				if (bns > 0 && i + j >= n)
					f2 = 1;
				//cout << i << " " << j << " " << a[i] << " " << b[j] << endl;
				if (b[j] == 0)
					j++;
				if (j == n)
					break;
			}
			if (i + j == n - 1)
				j++;
			if (j == n)
				break;
		}
		for (int i = 0; i < n;i++)
		{
			if(mxa+i>=n && b[i]>0)
			{
				f2 = 1;
				break;
			}
		}
			if (f2)
				cout << ans << endl;
			else
				cout << ans - 1 << endl;
	}
	__();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3820kb

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: 45ms
memory: 3668kb

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
4
3
3
2
0
0
1
1
3
0
3
0
0
0
0
0
0
0
4
0
4
1
0
2
4
3
1
5
0
0
2
0
0
1
1
0
0
3
5
3
2
2
2
0
1
2
2
2
0
4
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:

wrong answer 5th numbers differ - expected: '3', found: '4'