이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=300+10;
const int M=302*300;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e16;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=2027865967;
const int L=20;
int n;
ll t[N*2],l,doz[N*2][2];
int p1[M*2+10],p2[M*2+10];
void add(int val,ll il,bool xd){
if(!il) return;
bool rev=0;
for(int i=0;i<=M*2;i++){
p2[i]=-INFi;
}
if(val<0){
for(int i=0;i<M;i++){
swap(p1[i],p1[M*2-i]);
}
rev=1;
val*=(-1);
}
for(int i=0;i<val;i++){
deque<pair<int,int> >kol;
for(int i2=0;i2*val+i<=M*2;i2++){
int id=i2*val+i;
int cval=p1[id];
if(xd) cval-=i2;
else cval+=i2;
if(p1[id]!=-INFi){
while(kol.size() and kol.back().fi<=cval){
kol.pop_back();
}
kol.push_back({cval,i2});
}
if(kol.size() and i2-kol.front().se==il+1){
kol.pop_front();
}
if(kol.size()){
p2[id]=max(p2[id],(xd?i2:-i2)+kol.front().fi);
}
}
}
if(rev){
for(int i=0;i<M;i++){
swap(p1[i],p1[M*2-i]);
swap(p2[i],p2[M*2-i]);
}
}
for(int i=0;i<=M*2;i++){
p1[i]=max(p1[i],p2[i]);
}
}
ll pl(int val){
for(int i=0;i<=M*2;i++) p1[i]=-INFi;
p1[M]=0;
for(int i=0;i<=n*2;i++){
add(i-n,doz[i][0],0);
add(i-n,doz[i][1],1);
}
return p1[val+M];
}
void solve(){
cin>>n>>l;
ll sum=0;
for(int i=-n;i<=n;i++){
cin>>t[i+n];
sum+=t[i+n]*(ll)i;
}
if(sum<=l){
l*=(ll)(-1);
for(int i=0;i<n;i++){
swap(t[i],t[n*2-i]);
}
}
ll curr=0,res=0;
for(int i=-n;i<=n;i++){
if(i<=0){
curr+=t[i+n]*(ll)i;
doz[-i+n][0]+=t[i+n];
res+=t[i+n];
continue;
}
int id=i+n;
ll r=l-curr;
ll il=(r+i-1)/i;
il=min(il,t[i+n]);
curr+=il*(ll)i;
res+=il;
if(il==0){
doz[i+n][1]+=t[i+n];
continue;
}
if(il==t[i+n]){
doz[-i+n][0]+=t[i+n];
}else{
doz[-i+n][0]+=il;
doz[i+n][1]+=(t[i+n]-il);
}
}
if(abs(l-curr)>300){
cout<<"impossible\n";
return;
}
ll ans=pl(l-curr);
if(ans==-INFi) cout<<"impossible\n";
else cout<<res+ans<<"\n";
}
int main(){
ios_base::sync_with_stdio(0),cin.tie(0);
int tt=1;
while(tt--) solve();
}
컴파일 시 표준 에러 (stderr) 메시지
vault.cpp: In function 'void solve()':
vault.cpp:96:13: warning: unused variable 'id' [-Wunused-variable]
96 | int id=i+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... |