This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define MAX 1000005
int maximo[MAX];
int bonus = MAX/2;
typedef std::pair<int,int> pii;
int main()
{
long long N,M;
std::cin>>N>>M;
if(abs(M)>bonus){
std::cout<<"impossible\n";
return 0;
}
for(auto&x:maximo)x=-(1e6);
maximo[bonus]=0;
for(int i=-N;i<=N;++i){
int c;
std::cin>>c;
if(!c)continue;
int valor=abs(i);
if(!valor){
for(auto&x:maximo)x+=c;
continue;
}
std::deque<pii> vals[valor];
///Da direita para a esquerda
if(i>0){
for(int j=0;j!=MAX-1;++j){
int mod = j%valor;
int kok = j/valor;
int v = -(1e8);
while(vals[mod].size()){
if(kok-vals[mod].front().second>c){
vals[mod].pop_front();
continue;
}
v=vals[mod].front().first+kok;
break;
}
while(vals[mod].size()&&vals[mod].back().first<maximo[j]-kok)vals[mod].pop_back();
vals[mod].push_back({maximo[j]-kok,kok});
maximo[j]=std::max(maximo[j],v);
}
}else if(i<0){
for(int j=MAX-1;j!=-1;--j){
int mod = j%valor;
int kok = j/valor;
int v = -(1e8);
while(vals[mod].size()){
if(abs(kok-vals[mod].front().second)>c){
vals[mod].pop_front();
continue;
}
v=vals[mod].front().first-kok;
break;
}
while(vals[mod].size()&&vals[mod].back().first<maximo[j]+kok)vals[mod].pop_back();
vals[mod].push_back({maximo[j]+kok,kok});
maximo[j]=std::max(maximo[j],v);
}
}
}
///como proceder caso x=0?
if(maximo[M+bonus]<=0){
std::cout<<"impossible\n";
return 0;
}
std::cout<<maximo[M+bonus]<<"\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |