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 |
|
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 |