| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 58169 |
2018-07-17T05:14:21 Z |
윤교준(#1690) |
Candies (JOI18_candies) |
C++11 |
|
1956 ms |
129204 KB |
#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 allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#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 cb(x) (x)=(!(x))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
const int MAXN = 200005;
set<pli> PQ;
set<pil> CH;
ll A[MAXN];
ll Ans;
int N;
int main() {
ios::sync_with_stdio(false);
cin >> N;
for(int i = 1; i <= N; i++) cin >> A[i];
for(int i = 1; i <= N; i++) {
PQ.insert(pli(A[i], i));
CH.insert(pil(i, A[i]));
}
for(int i = 0; -N*2 <= i; i--) {
PQ.insert(pli(-INFLL, i));
CH.insert(pil(i, -INFLL));
}
for(int i = N+1; i <= N*3; i++) {
PQ.insert(pli(-INFLL, i));
CH.insert(pil(i, -INFLL));
}
for(int tc = 1; tc <= (N+1)/2; tc++) {
ll dst; int idx;
{
auto it = prev(PQ.end());
tie(dst, idx) = *it;
}
Ans += dst;
ll a = 0, b = dst, c = 0;
int ai = -1, bi = idx, ci = -1;
{
auto it = CH.lower_bound(pil(idx, dst));
{
if(CH.begin() != it) {
auto bt = prev(it);
tie(ai, a) = *bt;
}
}
{
auto bt = next(it);
if(CH.end() != bt) {
tie(ci, c) = *bt;
}
}
}
//if(ai < 0 || ci < 0) printf("SEX at %d :: %d\n", tc, bi);
//printf("tc=%d, sz=%d ; %d\n", tc, sz(CH), sz(PQ));
if(0 < ai) CH.erase(pil(ai, a));
if(0 < bi) CH.erase(pil(bi, b));
if(0 < ci) CH.erase(pil(ci, c));
if(0 < ai) PQ.erase(pli(a, ai));
if(0 < bi) PQ.erase(pli(b, bi));
if(0 < ci) PQ.erase(pli(c, ci));
CH.insert(pil(bi, a+c-b));
PQ.insert(pli(a+c-b, bi));
printf("%lld\n", Ans);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
1656 KB |
Output is correct |
| 2 |
Correct |
10 ms |
1772 KB |
Output is correct |
| 3 |
Correct |
10 ms |
1772 KB |
Output is correct |
| 4 |
Correct |
10 ms |
1792 KB |
Output is correct |
| 5 |
Correct |
9 ms |
1840 KB |
Output is correct |
| 6 |
Correct |
9 ms |
1840 KB |
Output is correct |
| 7 |
Correct |
8 ms |
1840 KB |
Output is correct |
| 8 |
Correct |
9 ms |
1908 KB |
Output is correct |
| 9 |
Correct |
10 ms |
1916 KB |
Output is correct |
| 10 |
Correct |
10 ms |
1940 KB |
Output is correct |
| 11 |
Correct |
13 ms |
1940 KB |
Output is correct |
| 12 |
Correct |
10 ms |
1964 KB |
Output is correct |
| 13 |
Correct |
10 ms |
1964 KB |
Output is correct |
| 14 |
Correct |
9 ms |
1964 KB |
Output is correct |
| 15 |
Correct |
9 ms |
1964 KB |
Output is correct |
| 16 |
Correct |
11 ms |
1964 KB |
Output is correct |
| 17 |
Correct |
10 ms |
1964 KB |
Output is correct |
| 18 |
Correct |
10 ms |
1964 KB |
Output is correct |
| 19 |
Correct |
9 ms |
1964 KB |
Output is correct |
| 20 |
Correct |
13 ms |
1964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
1656 KB |
Output is correct |
| 2 |
Correct |
10 ms |
1772 KB |
Output is correct |
| 3 |
Correct |
10 ms |
1772 KB |
Output is correct |
| 4 |
Correct |
10 ms |
1792 KB |
Output is correct |
| 5 |
Correct |
9 ms |
1840 KB |
Output is correct |
| 6 |
Correct |
9 ms |
1840 KB |
Output is correct |
| 7 |
Correct |
8 ms |
1840 KB |
Output is correct |
| 8 |
Correct |
9 ms |
1908 KB |
Output is correct |
| 9 |
Correct |
10 ms |
1916 KB |
Output is correct |
| 10 |
Correct |
10 ms |
1940 KB |
Output is correct |
| 11 |
Correct |
13 ms |
1940 KB |
Output is correct |
| 12 |
Correct |
10 ms |
1964 KB |
Output is correct |
| 13 |
Correct |
10 ms |
1964 KB |
Output is correct |
| 14 |
Correct |
9 ms |
1964 KB |
Output is correct |
| 15 |
Correct |
9 ms |
1964 KB |
Output is correct |
| 16 |
Correct |
11 ms |
1964 KB |
Output is correct |
| 17 |
Correct |
10 ms |
1964 KB |
Output is correct |
| 18 |
Correct |
10 ms |
1964 KB |
Output is correct |
| 19 |
Correct |
9 ms |
1964 KB |
Output is correct |
| 20 |
Correct |
13 ms |
1964 KB |
Output is correct |
| 21 |
Correct |
1956 ms |
129056 KB |
Output is correct |
| 22 |
Correct |
1919 ms |
129156 KB |
Output is correct |
| 23 |
Correct |
1953 ms |
129156 KB |
Output is correct |
| 24 |
Correct |
1314 ms |
129156 KB |
Output is correct |
| 25 |
Correct |
1295 ms |
129156 KB |
Output is correct |
| 26 |
Correct |
1255 ms |
129156 KB |
Output is correct |
| 27 |
Correct |
1275 ms |
129156 KB |
Output is correct |
| 28 |
Correct |
1201 ms |
129156 KB |
Output is correct |
| 29 |
Correct |
1287 ms |
129156 KB |
Output is correct |
| 30 |
Correct |
1242 ms |
129156 KB |
Output is correct |
| 31 |
Correct |
1248 ms |
129156 KB |
Output is correct |
| 32 |
Correct |
1256 ms |
129156 KB |
Output is correct |
| 33 |
Correct |
1469 ms |
129156 KB |
Output is correct |
| 34 |
Correct |
1507 ms |
129156 KB |
Output is correct |
| 35 |
Correct |
1541 ms |
129156 KB |
Output is correct |
| 36 |
Correct |
1764 ms |
129156 KB |
Output is correct |
| 37 |
Correct |
1859 ms |
129204 KB |
Output is correct |
| 38 |
Correct |
1787 ms |
129204 KB |
Output is correct |
| 39 |
Correct |
1182 ms |
129204 KB |
Output is correct |
| 40 |
Correct |
1165 ms |
129204 KB |
Output is correct |
| 41 |
Correct |
1172 ms |
129204 KB |
Output is correct |
| 42 |
Correct |
1276 ms |
129204 KB |
Output is correct |
| 43 |
Correct |
1307 ms |
129204 KB |
Output is correct |
| 44 |
Correct |
1205 ms |
129204 KB |
Output is correct |
| 45 |
Correct |
1324 ms |
129204 KB |
Output is correct |
| 46 |
Correct |
1272 ms |
129204 KB |
Output is correct |
| 47 |
Correct |
1240 ms |
129204 KB |
Output is correct |
| 48 |
Correct |
1421 ms |
129204 KB |
Output is correct |
| 49 |
Correct |
1492 ms |
129204 KB |
Output is correct |
| 50 |
Correct |
1511 ms |
129204 KB |
Output is correct |
