| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 95323 |
2019-01-30T05:51:20 Z |
Retro3014 |
None (JOI14_ho_t3) |
C++17 |
|
465 ms |
3064 KB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <deque>
using namespace std;
typedef long long ll;
#define MAX_N 100000
int N;
deque<ll> dq;
ll sum[MAX_N+1], ans;
ll calc(int x, int y){
if(x<=y){
if(x==0) return sum[y];
else return sum[y]-sum[x-1];
}else{
return sum[y]+sum[N-1]-sum[x-1];
}
}
ll calc2(int x, int y){
ll ret = 0;
int s = 0, e = y, m;
while(s<e){
m = (s+e)/2;
ll s1 = calc(x, (x+m)%N), s2 = calc((x+m+1)%N, (x+y)%N);
ret = max(ret, min(s1, s2));
if(s1<=s2) s = m+1;
else e = m;
}
return ret;
}
int main(){
scanf("%d", &N);
for(int i=0; i<N; i++){
ll x;
scanf("%lld", &x);
dq.push_back(x);
}
for(int i=0; i<dq.size(); i++){
if(i==0) sum[i] = dq[i];
else sum[i] = sum[i-1]+dq[i];
}
for(int st=0; st<N; st++){
if(calc2((st+1)%N, N-2)<calc(st, st)) continue;
int s = 0, e = N-1, m;
while(s<e){
m = (s+e)/2+1;
if(calc2((st+m+1)%N, N-1-(m+1)%N)>=calc(st, (st+m)%N)){
s = m;
}else{
e = m-1;
}
}
//cout<<st<<" "<<s<<endl;
ans = max(ans, calc(st, (st+s)%N));
}
printf("%lld", ans);
return 0;
}
Compilation message
2014_ho_t3.cpp: In function 'int main()':
2014_ho_t3.cpp:45:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<dq.size(); i++){
~^~~~~~~~~~
2014_ho_t3.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
2014_ho_t3.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &x);
~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
256 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
380 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
256 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
380 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
3 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
360 KB |
Output is correct |
| 17 |
Correct |
2 ms |
376 KB |
Output is correct |
| 18 |
Correct |
3 ms |
376 KB |
Output is correct |
| 19 |
Correct |
2 ms |
376 KB |
Output is correct |
| 20 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
256 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
380 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
3 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
360 KB |
Output is correct |
| 17 |
Correct |
2 ms |
376 KB |
Output is correct |
| 18 |
Correct |
3 ms |
376 KB |
Output is correct |
| 19 |
Correct |
2 ms |
376 KB |
Output is correct |
| 20 |
Correct |
2 ms |
376 KB |
Output is correct |
| 21 |
Correct |
24 ms |
504 KB |
Output is correct |
| 22 |
Correct |
24 ms |
504 KB |
Output is correct |
| 23 |
Correct |
23 ms |
504 KB |
Output is correct |
| 24 |
Correct |
24 ms |
504 KB |
Output is correct |
| 25 |
Correct |
24 ms |
632 KB |
Output is correct |
| 26 |
Correct |
24 ms |
504 KB |
Output is correct |
| 27 |
Correct |
24 ms |
608 KB |
Output is correct |
| 28 |
Correct |
24 ms |
508 KB |
Output is correct |
| 29 |
Correct |
24 ms |
504 KB |
Output is correct |
| 30 |
Correct |
24 ms |
504 KB |
Output is correct |
| 31 |
Correct |
26 ms |
504 KB |
Output is correct |
| 32 |
Correct |
27 ms |
508 KB |
Output is correct |
| 33 |
Correct |
27 ms |
504 KB |
Output is correct |
| 34 |
Correct |
26 ms |
508 KB |
Output is correct |
| 35 |
Correct |
26 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
256 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
380 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
3 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
360 KB |
Output is correct |
| 17 |
Correct |
2 ms |
376 KB |
Output is correct |
| 18 |
Correct |
3 ms |
376 KB |
Output is correct |
| 19 |
Correct |
2 ms |
376 KB |
Output is correct |
| 20 |
Correct |
2 ms |
376 KB |
Output is correct |
| 21 |
Correct |
24 ms |
504 KB |
Output is correct |
| 22 |
Correct |
24 ms |
504 KB |
Output is correct |
| 23 |
Correct |
23 ms |
504 KB |
Output is correct |
| 24 |
Correct |
24 ms |
504 KB |
Output is correct |
| 25 |
Correct |
24 ms |
632 KB |
Output is correct |
| 26 |
Correct |
24 ms |
504 KB |
Output is correct |
| 27 |
Correct |
24 ms |
608 KB |
Output is correct |
| 28 |
Correct |
24 ms |
508 KB |
Output is correct |
| 29 |
Correct |
24 ms |
504 KB |
Output is correct |
| 30 |
Correct |
24 ms |
504 KB |
Output is correct |
| 31 |
Correct |
26 ms |
504 KB |
Output is correct |
| 32 |
Correct |
27 ms |
508 KB |
Output is correct |
| 33 |
Correct |
27 ms |
504 KB |
Output is correct |
| 34 |
Correct |
26 ms |
508 KB |
Output is correct |
| 35 |
Correct |
26 ms |
504 KB |
Output is correct |
| 36 |
Correct |
418 ms |
2936 KB |
Output is correct |
| 37 |
Correct |
424 ms |
2964 KB |
Output is correct |
| 38 |
Correct |
435 ms |
2944 KB |
Output is correct |
| 39 |
Correct |
422 ms |
3064 KB |
Output is correct |
| 40 |
Correct |
421 ms |
3064 KB |
Output is correct |
| 41 |
Correct |
434 ms |
2944 KB |
Output is correct |
| 42 |
Correct |
431 ms |
2944 KB |
Output is correct |
| 43 |
Correct |
428 ms |
2836 KB |
Output is correct |
| 44 |
Correct |
432 ms |
3064 KB |
Output is correct |
| 45 |
Correct |
421 ms |
2936 KB |
Output is correct |
| 46 |
Correct |
465 ms |
2168 KB |
Output is correct |
| 47 |
Correct |
461 ms |
2168 KB |
Output is correct |
| 48 |
Correct |
459 ms |
2168 KB |
Output is correct |
