Submission #2949216


Source Code Expand

#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define befv(V) ((V)[(sz(V)-2)])
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef __int128_t lll;
typedef long double ld;
typedef pair<int, int> pii;

const int MAXN = 200055;

priority_queue<ll, vector<ll>, greater<ll>> PQ[2];

ll A[MAXN], B[MAXN];

lll Ans;
int N;

int main() {
	ios::sync_with_stdio(false);

	cin >> N;
	for(int i = 2; i <= N; i++) {
		cin >> A[i];
		A[i] += A[i-1];
	}
	for(int i = 1; i <= N; i++) cin >> B[i];

	for(int i = 1; i <= N; i++) {
		for(int _ = 0; _ < 2; _++) {
			if(!PQ[0].empty() && A[i] + B[i] + PQ[0].top() <= 0) {
				ll t = PQ[0].top(); PQ[0].pop();
				Ans += A[i] + B[i] + t;
				PQ[1].push(-A[i]*2 - t);
				PQ[0].push(-A[i] - B[i]);
			} else PQ[1].push(B[i] - A[i]);
		}
		ll t = PQ[1].top(); PQ[1].pop();
		Ans += A[i] + t;
		PQ[0].push(-A[i]*2 - t);
	}

	cout << ll(Ans) << endl;
	return 0;
}

Submission Info

Submission Time
Task J - Farm Village
User youngyojun
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1427 Byte
Status AC
Exec Time 85 ms
Memory 6756 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 53
Set Name Test Cases
All 00_sample_00, 00_sample_01, 00_sample_02, 10_small_0, 10_small_1, 10_small_2, 10_small_3, 10_small_4, 10_small_5, 10_small_6, 10_small_7, 10_small_8, 10_small_9, 20_medium_0, 20_medium_1, 20_medium_2, 20_medium_3, 20_medium_4, 20_medium_5, 20_medium_6, 20_medium_7, 20_medium_8, 20_medium_9, 30_large_0, 30_large_1, 30_large_2, 30_large_3, 30_large_4, 30_large_5, 30_large_6, 30_large_7, 30_large_8, 30_large_9, 50_biased_0, 50_biased_1, 50_biased_10, 50_biased_11, 50_biased_12, 50_biased_13, 50_biased_14, 50_biased_15, 50_biased_16, 50_biased_17, 50_biased_18, 50_biased_19, 50_biased_2, 50_biased_3, 50_biased_4, 50_biased_5, 50_biased_6, 50_biased_7, 50_biased_8, 50_biased_9
Case Name Status Exec Time Memory
00_sample_00 AC 2 ms 380 KB
00_sample_01 AC 1 ms 256 KB
00_sample_02 AC 1 ms 256 KB
10_small_0 AC 1 ms 256 KB
10_small_1 AC 1 ms 256 KB
10_small_2 AC 1 ms 256 KB
10_small_3 AC 1 ms 256 KB
10_small_4 AC 1 ms 256 KB
10_small_5 AC 1 ms 256 KB
10_small_6 AC 1 ms 256 KB
10_small_7 AC 1 ms 256 KB
10_small_8 AC 1 ms 256 KB
10_small_9 AC 1 ms 256 KB
20_medium_0 AC 1 ms 256 KB
20_medium_1 AC 2 ms 256 KB
20_medium_2 AC 1 ms 256 KB
20_medium_3 AC 1 ms 256 KB
20_medium_4 AC 1 ms 256 KB
20_medium_5 AC 1 ms 256 KB
20_medium_6 AC 1 ms 256 KB
20_medium_7 AC 1 ms 256 KB
20_medium_8 AC 1 ms 256 KB
20_medium_9 AC 1 ms 256 KB
30_large_0 AC 71 ms 6380 KB
30_large_1 AC 41 ms 3820 KB
30_large_2 AC 41 ms 3820 KB
30_large_3 AC 4 ms 640 KB
30_large_4 AC 75 ms 6636 KB
30_large_5 AC 60 ms 5996 KB
30_large_6 AC 49 ms 4460 KB
30_large_7 AC 67 ms 6252 KB
30_large_8 AC 12 ms 1404 KB
30_large_9 AC 32 ms 3316 KB
50_biased_0 AC 83 ms 6756 KB
50_biased_1 AC 85 ms 6756 KB
50_biased_10 AC 84 ms 6756 KB
50_biased_11 AC 83 ms 6756 KB
50_biased_12 AC 83 ms 6756 KB
50_biased_13 AC 83 ms 6756 KB
50_biased_14 AC 84 ms 6756 KB
50_biased_15 AC 84 ms 6756 KB
50_biased_16 AC 83 ms 6756 KB
50_biased_17 AC 83 ms 6756 KB
50_biased_18 AC 83 ms 6756 KB
50_biased_19 AC 83 ms 6756 KB
50_biased_2 AC 84 ms 6756 KB
50_biased_3 AC 83 ms 6756 KB
50_biased_4 AC 83 ms 6756 KB
50_biased_5 AC 83 ms 6756 KB
50_biased_6 AC 83 ms 6756 KB
50_biased_7 AC 83 ms 6756 KB
50_biased_8 AC 83 ms 6756 KB
50_biased_9 AC 83 ms 6756 KB