Submission #743614

#	Time	Username	Problem	Language	Result	Execution time	Memory
743614		flappybird	Rainy Markets (CCO22_day1problem2)	C++17	0 / 25	1561 ms	61084 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 1001010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
ll B[MAX];
ll S[MAX];
ll P[MAX];
ll U[MAX];
ll add[MAX];
ll used[MAX];
ll cur[MAX];
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N;
	cin >> N;
	int i;
	for (i = 1; i <= N; i++) cin >> B[i], S[i] = S[i - 1] + B[i];
	for (i = 1; i < N; i++) cin >> P[i];
	for (i = 1; i < N; i++) cin >> U[i];
	ll ans = 0;
	for (i = 1; i <= N; i++) add[i] = min(U[i], P[i]), P[i] -= add[i], ans += add[i];
	for (i = 1; i < N; i++) {
		int j;
		ll mn = add[i];
		ll sum = 0;
		for (j = i; j >= 1; j--) {
			sum += used[j] + P[j];
			mn = min(mn, S[i + 1] - S[j - 1] - sum);
		}
		if (mn < 0) {
			cout << "NO" << ln;
			return 0;
		}
		used[i] = mn;
		ans -= mn;
	}
	cout << "YES" << ln;
	cout << ans << ln;
	for (i = 1; i < N; i++) {
		P[i] += used[i];
		ll left = min(P[i], B[i] - cur[i]);
		ll right = P[i] - left;
		cout << left << bb << add[i] - used[i] << bb << right << ln;
		cur[i + 1] += right;
	}
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 6
• Subtask 4: 0 / 9