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::priority_queue<pii> vals[valor];
///Da direita para a esquerda
if(i>0){
for(int j=0;j!=MAX-1;++j){
if(j-i<0)continue;
int mod = j%valor;
int kok = j/valor;
int v = -1;
while(vals[mod].size()){
if(kok-vals[mod].top().second>c){
vals[mod].pop();
continue;
}
v=vals[mod].top().first+kok;
break;
}
vals[mod].push({maximo[j]-kok,kok});
maximo[j]=std::max(maximo[j],v);
}
}else if(i<0){
for(int j=MAX-1;j!=-1;--j){
if(j-i<0)continue;
int mod = j%valor;
int kok = j/valor;
int v = -1;
while(vals[mod].size()){
if(abs(kok-vals[mod].top().second)>c){
vals[mod].pop();
continue;
}
v=vals[mod].top().first-kok;
break;
}
vals[mod].push({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... |