| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 953812 | PM1 | Uplifting Excursion (BOI22_vault) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fr first
#define sc second
const int mxn=305;
ll m,a[mxn*2],l,sum,ans,num;
vector<pair<ll,ll>>v;
ll dp[2][mxn*mxn*2];
void add(ll tedad,ll x,ll z){
tedad=(min(tedad,m*2));
for(ll i=1;i<=tedad;i*=2){
v.push_back({i*x,z*i});
tedad-=i;
}
if(tedad>0)
v.push_back({tedad*x,z*tedad});
}
void solve(){
for(ll i=m;i<2*m+1;i++){
ans+=a[i];
num+=a[i]*(i-m);
add(a[i],-(i-m),-1);
}
ll i=m-1;
for(;i>=0;i--){
if(num+a[i]*(i-m)>=l){
ans+=a[i];
num+=a[i]*(i-m);
add(a[i],-(i-m),-1);
continue;
}
ll x=l-num;
x=x/(i-m);
x=min(x,a[i]);
num+=a[i]*x;
ans+=x;
add(x,-(i-m),-1);
add(a[i]-x,i-m,1);
i--;
break;
}
for(;i>=0;i--){
add(a[i],(i-m),1);
}
}
void solve1(){
for(ll i=m;i>=0;i--){
ans+=a[i];
num+=a[i]*(i-m);
add(a[i],-(i-m),-1);
}
ll i=m+1;
for(;i<m*2+1;i++){
if(num+a[i]*(i-m)<=l){
ans+=a[i];
num+=a[i]*(i-m);
add(a[i],-(i-m),-1);
continue;
}
ll x=l-num;
x=x/(i-m);
x=max(x,0);
x=min(x,a[i]);
num+=(i-m)*x;
ans+=x;
add(x,-(i-m),-1);
add(a[i]-x,i-m,1);
i++;
break;
}
for(;i<m*2+1;i++){
add(a[i],(i-m),1);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>m>>l;
for(ll i=0;i<m*2+1;i++){
cin>>a[i];
sum+=(i-m)*a[i];
}
if(sum<=l)
solve();
else
solve1();
for(int i=0;i<=2*m*m;i++)dp[1][i]=-1e18;
dp[1][m*m]=0;
for(int i=0;i<v.size();i++){
ll x=v[i].fr,y=v[i].sc;
int z=i&1;
for(ll j=0;j<=2*m*m;j++){
if(j-x>=0 && j-x<=2*m*m && dp[z^1][j-x]!=-1e18)
dp[z][j]=max(dp[z^1][j],dp[z^1][j-x]+y);
else
dp[z][j]=dp[z^1][j];
}
//cout<<dp[z][928]<<" ";
}
int x=v.size()&1;
x^=1;
l-=num;
if( l>m*m || l<-m*m ||dp[x][l+m*m]==-1e18 || ans+dp[x][l+m*m]<0){
cout<<"impossible";
return 0;
}
cout<<ans+dp[x][l+m*m];
return 0;
}