#include <bits/stdc++.h>
#define MAX 2100000
#define LSB(A) (A&(-A))
using ll = long long;
typedef std::pair<ll,ll> pll;
typedef std::pair<ll,pll> plp;
ll ft[MAX];
void update(int t,int k){t+=8;
while(t<MAX){
ft[t]+=k;
t+=LSB(t);
}
}
ll query(int t){t+=8;
ll ans=0;
while(t>0){
ans+=ft[t];
t-=LSB(t);
}
return ans;
}
ll seg(int l,int r){
return query(r)-query(l-1);
}
ll array[MAX];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int N;
std::cin>>N;
long long soma=0;
for(int i=0;i!=N;++i){
std::cin>>array[i];
soma+=array[i];
}
for(int i=0;i!=MAX;++i){
array[i]=array[i%N];
}
for(int i=0;i!=MAX;++i){
update(i,array[i]);
}
ll respostas[N]={};
ll puxa=N/2;
ll ans=0;
ll left[N]={},right[N]={};
for(int i=0;i!=N;++i){
respostas[i]=seg(i,i+puxa-1);
/// std::cout<<i<<" "<<i+puxa-1<<" "<<respostas[i]<<"\n";
if(i){
left[i-1]=std::max(left[i-1],respostas[i]);
}
if(i+puxa<N){
right[i+puxa]=std::max(right[i+puxa],respostas[i]);
}
}
ll total[N]={};
{
ll p=0;
for(int i=0;i!=N;++i){
p=std::max(p,right[i]);
total[i]=std::max(total[i],p);
}
p=0;
for(int i=N-1;i!=-1;--i){
p=std::max(p,left[i]);
total[i]=std::max(total[i],p);
}
/* for(int i=0;i!=N;++i){
std::cout<<total[i]<<" ";
}
std::cout<<"\n";*/
}
std::cout<<(soma-(*std::min_element(total,&total[N])))<<"\n";
}
Compilation message
hac.cpp: In function 'int main()':
hac.cpp:46:8: warning: unused variable 'ans' [-Wunused-variable]
46 | ll ans=0;
| ^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
67 ms |
33168 KB |
Output is correct |
2 |
Correct |
72 ms |
33152 KB |
Output is correct |
3 |
Correct |
73 ms |
33136 KB |
Output is correct |
4 |
Correct |
71 ms |
33100 KB |
Output is correct |
5 |
Correct |
69 ms |
33080 KB |
Output is correct |
6 |
Correct |
69 ms |
33136 KB |
Output is correct |
7 |
Correct |
69 ms |
33132 KB |
Output is correct |
8 |
Correct |
83 ms |
33212 KB |
Output is correct |
9 |
Correct |
68 ms |
33164 KB |
Output is correct |
10 |
Correct |
66 ms |
33124 KB |
Output is correct |
11 |
Correct |
69 ms |
33096 KB |
Output is correct |
12 |
Incorrect |
74 ms |
33228 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
67 ms |
33168 KB |
Output is correct |
2 |
Correct |
72 ms |
33152 KB |
Output is correct |
3 |
Correct |
73 ms |
33136 KB |
Output is correct |
4 |
Correct |
71 ms |
33100 KB |
Output is correct |
5 |
Correct |
69 ms |
33080 KB |
Output is correct |
6 |
Correct |
69 ms |
33136 KB |
Output is correct |
7 |
Correct |
69 ms |
33132 KB |
Output is correct |
8 |
Correct |
83 ms |
33212 KB |
Output is correct |
9 |
Correct |
68 ms |
33164 KB |
Output is correct |
10 |
Correct |
66 ms |
33124 KB |
Output is correct |
11 |
Correct |
69 ms |
33096 KB |
Output is correct |
12 |
Incorrect |
74 ms |
33228 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
72 ms |
33164 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
67 ms |
33168 KB |
Output is correct |
2 |
Correct |
72 ms |
33152 KB |
Output is correct |
3 |
Correct |
73 ms |
33136 KB |
Output is correct |
4 |
Correct |
71 ms |
33100 KB |
Output is correct |
5 |
Correct |
69 ms |
33080 KB |
Output is correct |
6 |
Correct |
69 ms |
33136 KB |
Output is correct |
7 |
Correct |
69 ms |
33132 KB |
Output is correct |
8 |
Correct |
83 ms |
33212 KB |
Output is correct |
9 |
Correct |
68 ms |
33164 KB |
Output is correct |
10 |
Correct |
66 ms |
33124 KB |
Output is correct |
11 |
Correct |
69 ms |
33096 KB |
Output is correct |
12 |
Incorrect |
74 ms |
33228 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |