| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 335002 |
2020-12-10T18:11:03 Z |
Plurm |
Candies (JOI18_candies) |
C++11 |
|
5000 ms |
28140 KB |
#include <bits/stdc++.h>
using namespace std;
int a[200005];
struct state{
int u, v;
long long nw, ow;
state(int x, int y, long long z, long long t) : u(x), v(y), nw(z), ow(t) {}
friend bool operator<(const state& x, const state& y){
if(x.nw - x.ow != y.nw - y.ow) return x.nw - x.ow < y.nw - y.ow;
return make_pair(x.u, x.v) < make_pair(y.u, y.v);
}
};
set<pair<int,int> > ranges; // picked ranges
set<pair<int,int> > options; // potential options (sorted by pair)
set<state> states; // potential options
set<pair<int,int> >::iterator isCovered(int x){
// checks whether x is covered?
auto it = ranges.upper_bound(make_pair(x, 1000000));
if(it == ranges.begin()) return ranges.end();
it--;
return it->second >= x ? it : ranges.end();
}
set<pair<int,int> >::iterator isOptionsCovered(int x){
// checks whether x is covered?
auto it = options.upper_bound(make_pair(x, 1000000));
if(it == options.begin()) return options.end();
it--;
return it->second >= x ? it : options.end();
}
long long qs[200005];
long long qsx[200005];
inline long long getSum(int idx){
return idx > 0 ? qsx[idx] : 0ll;
}
int main(){
int n;
scanf("%d",&n);
for(int i = 1; i <= n; i++){
scanf("%d",a+i);
states.emplace(i,i,a[i],0);
options.emplace(i,i);
qsx[i] = (i-2 > 0 ? qsx[i-2] : 0ll) + a[i];
qs[i] = qs[i-1] + a[i];
}
long long ans = 0ll;
for(int turn = 1; turn <= (n+1)/2; turn++){
// DEBUG
//printf("RANGES\n");
for(auto r : ranges){
//printf("%d %d\n", r.first, r.second);
}
//printf("OPTIONS\n");
for(auto r : options){
//printf("%d %d\n", r.first, r.second);
}
//printf("STATES\n");
for(auto r : states){
//printf("%d %d %lld\n", r.u, r.v, r.nw - r.ow);
}
//printf("===\n");
auto cur = *states.rbegin(); // maximum potential weight
//printf("Picked %d, %d at step %d\n", cur.u, cur.v, turn);
ans += cur.nw - cur.ow;
states.erase(cur);
options.erase(make_pair(cur.u, cur.v));
ranges.erase(make_pair(cur.u+1, cur.v-1));
// left-joinable and right-joinable?
auto lchk = cur.u > 1 ? isCovered(cur.u - 2) : ranges.end();
auto rchk = cur.v < n ? isCovered(cur.v + 2) : ranges.end();
int targetL = lchk == ranges.end() ? cur.u : lchk->first;
int targetR = rchk == ranges.end() ? cur.v : rchk->second;
if(lchk != ranges.end()){
ranges.erase(lchk);
}
auto p = isOptionsCovered(cur.u-1);
// find the props of the state
if(p != options.end()){
long long nw = getSum(p->second) - getSum(p->first - 2);
long long ow = qs[p->second] - qs[p->first-1] - nw;
state ex(p->first, p->second, nw, ow);
states.erase(ex);
options.erase(p);
}
if(rchk != ranges.end()){
ranges.erase(rchk);
}
p = isOptionsCovered(cur.v+1);
if(p != options.end()){
// find the props of the state
long long nw = getSum(p->second) - getSum(p->first - 2);
long long ow = qs[p->second] - qs[p->first-1] - nw;
state ex(p->first, p->second, nw, ow);
states.erase(ex);
options.erase(p);
}
ranges.emplace(targetL, targetR);
if(targetL-1 >= 1 && targetR+1 <= n){
options.emplace(targetL-1, targetR+1);
long long cow = getSum(targetR) - getSum(targetL-2);
states.emplace(targetL-1, targetR+1, qs[targetR+1] - qs[targetL-2] - cow, cow);
}
printf("%lld\n", ans);
}
//printf("RANGES\n");
for(auto r : ranges){
//printf("%d %d\n", r.first, r.second);
}
//printf("OPTIONS\n");
for(auto r : options){
//printf("%d %d\n", r.first, r.second);
}
//printf("STATES\n");
for(auto r : states){
//printf("%d %d\n", r.u, r.v);
}
//printf("===\n");
return 0;
}
Compilation message
candies.cpp: In function 'int main()':
candies.cpp:49:12: warning: variable 'r' set but not used [-Wunused-but-set-variable]
49 | for(auto r : ranges){
| ^
candies.cpp:53:12: warning: variable 'r' set but not used [-Wunused-but-set-variable]
53 | for(auto r : options){
| ^
candies.cpp:57:12: warning: variable 'r' set but not used [-Wunused-but-set-variable]
57 | for(auto r : states){
| ^
candies.cpp:106:11: warning: variable 'r' set but not used [-Wunused-but-set-variable]
106 | for(auto r : ranges){
| ^
candies.cpp:110:11: warning: variable 'r' set but not used [-Wunused-but-set-variable]
110 | for(auto r : options){
| ^
candies.cpp:114:11: warning: variable 'r' set but not used [-Wunused-but-set-variable]
114 | for(auto r : states){
| ^
candies.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
37 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
candies.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
39 | scanf("%d",a+i);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
620 KB |
Output is correct |
| 2 |
Correct |
27 ms |
620 KB |
Output is correct |
| 3 |
Correct |
26 ms |
620 KB |
Output is correct |
| 4 |
Correct |
26 ms |
748 KB |
Output is correct |
| 5 |
Correct |
28 ms |
620 KB |
Output is correct |
| 6 |
Correct |
30 ms |
896 KB |
Output is correct |
| 7 |
Correct |
26 ms |
620 KB |
Output is correct |
| 8 |
Correct |
26 ms |
620 KB |
Output is correct |
| 9 |
Correct |
24 ms |
620 KB |
Output is correct |
| 10 |
Correct |
22 ms |
620 KB |
Output is correct |
| 11 |
Correct |
29 ms |
620 KB |
Output is correct |
| 12 |
Correct |
34 ms |
620 KB |
Output is correct |
| 13 |
Correct |
33 ms |
620 KB |
Output is correct |
| 14 |
Correct |
25 ms |
620 KB |
Output is correct |
| 15 |
Correct |
27 ms |
620 KB |
Output is correct |
| 16 |
Correct |
28 ms |
620 KB |
Output is correct |
| 17 |
Correct |
26 ms |
620 KB |
Output is correct |
| 18 |
Correct |
26 ms |
748 KB |
Output is correct |
| 19 |
Correct |
26 ms |
640 KB |
Output is correct |
| 20 |
Correct |
21 ms |
620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
620 KB |
Output is correct |
| 2 |
Correct |
27 ms |
620 KB |
Output is correct |
| 3 |
Correct |
26 ms |
620 KB |
Output is correct |
| 4 |
Correct |
26 ms |
748 KB |
Output is correct |
| 5 |
Correct |
28 ms |
620 KB |
Output is correct |
| 6 |
Correct |
30 ms |
896 KB |
Output is correct |
| 7 |
Correct |
26 ms |
620 KB |
Output is correct |
| 8 |
Correct |
26 ms |
620 KB |
Output is correct |
| 9 |
Correct |
24 ms |
620 KB |
Output is correct |
| 10 |
Correct |
22 ms |
620 KB |
Output is correct |
| 11 |
Correct |
29 ms |
620 KB |
Output is correct |
| 12 |
Correct |
34 ms |
620 KB |
Output is correct |
| 13 |
Correct |
33 ms |
620 KB |
Output is correct |
| 14 |
Correct |
25 ms |
620 KB |
Output is correct |
| 15 |
Correct |
27 ms |
620 KB |
Output is correct |
| 16 |
Correct |
28 ms |
620 KB |
Output is correct |
| 17 |
Correct |
26 ms |
620 KB |
Output is correct |
| 18 |
Correct |
26 ms |
748 KB |
Output is correct |
| 19 |
Correct |
26 ms |
640 KB |
Output is correct |
| 20 |
Correct |
21 ms |
620 KB |
Output is correct |
| 21 |
Execution timed out |
5064 ms |
28140 KB |
Time limit exceeded |
| 22 |
Halted |
0 ms |
0 KB |
- |
