제출 #594958

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
594958		azberjibiou	Uplifting Excursion (BOI22_vault)	C++17	40 / 100	1792 ms	5068 KiB

vault

#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fir first
#define sec second
#define pdd pair<long double, long double>
#define pii pair<int, int>
#define pll pair<ll, ll>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
const int mxN=303;
const int MOD=1e9+7;
ll M, L;
ll A[2*mxN];
ll nval, ncnt;
vector <pll> minu, plu;
int dp[mxN*mxN];
int sps[mxN*mxN][12];
void make_sps(int jump, int buho)
{
    for(int i=L-nval;i<=M*M;i++)    sps[i+mxN][0]=dp[i+mxN]-((i+mxN)/jump)*buho;
    for(int i=1;i<12;i++)
    {
        for(int j=L-nval;j<=M*M;j++)
        {
            if(j-(1<<i)*jump>=L-nval)   sps[j+mxN][i]=max(sps[j+mxN][i-1], sps[j-(1<<i-1)*jump+mxN][i-1]);
            else    sps[j+mxN][i]=sps[j+mxN][i-1];
        }
    }
}
int solv(int st, int wid, int jump)
{
    int ret=-MOD;
    for(int i=11;i>=0;i--)
    {
        if(wid>=(1<<i))
        {
            wid-=(1<<i);
            ret=max(ret, sps[st][i]);
            st-=jump*(1<<i);
        }
    }
    return ret;
}
int main()
{
    gibon
    cin >> M >> L;
    for(int i=-M;i<=M;i++)  cin >> A[i+mxN];
    ll psum=0, msum=0;
    for(int i=-M;i<0;i++)   msum+=i*A[i+mxN];
    for(int i=1;i<=M;i++)   psum+=i*A[i+mxN];
    if(L>psum || L<msum)    {cout << "impossible";  return 0;}
    if(L==msum+psum)
    {
        ll tmp=0;
        for(int i=-M;i<=M;i++)  tmp+=A[i+mxN];
        cout << tmp;    return 0;
    }
    if(L>msum+psum)
    {
        L*=-1;
        for(int i=1;i<=M;i++)   swap(A[i+mxN], A[-i+mxN]);
    }
    for(int i=-M;i<0;i++)   minu.emplace_back(i, A[i+mxN]);
    for(ll i=-M;i<0;i++)   nval+=A[i+mxN]*i, ncnt+=A[i+mxN];
    for(int i=1;i<=M;i++)
    {
        if(nval>L)
        {
            plu.emplace_back(i, A[i+mxN]);
            continue;
        }
        if(L-nval>i*A[i+mxN])   nval+=i*A[i+mxN], ncnt+=A[i+mxN], minu.emplace_back(i, A[i+mxN]);
        else if((L-nval)%i==0)
        {
            ncnt+=(L-nval)/i;
            cout << ncnt+A[mxN];
            return 0;
        }
        else
        {
            minu.emplace_back(i, (L-nval)/i+1);
            plu.emplace_back(i, A[i+mxN]-(L-nval)/i-1);
            ncnt+=(L-nval)/i+1;
            nval+=i*((L-nval)/i+1);
        }
    }
    for(int i=L-nval;i<=M*M;i++)    dp[i+mxN]=-MOD;
    dp[mxN]=0;
    for(pll ele : plu)
    {
        make_sps(ele.fir, 1);
        for(int i=M*M;i>=L-nval;i--)
        {
            int wid=min(ele.sec, (i-(L-nval))/ele.fir);
            if(wid==0)  continue;
            dp[i+mxN]=max((ll)dp[i+mxN], solv(i+mxN-ele.fir, wid, ele.fir)+(i+mxN)/ele.fir);
            //for(int j=1;j<=min(ele.sec, (i-(L-nval))/ele.fir);j++)  dp[i+mxN]=max(dp[i+mxN], dp[i+mxN-j*ele.fir]+j);
        }
    }
    for(pll ele : minu)
    {
        if(ele.fir<0)
        {
            make_sps(-ele.fir, -1);
            for(int i=M*M;i>=L-nval;i--)
            {
                int wid=min(ele.sec, (i-(L-nval))/(-ele.fir));
                if(wid==0)  continue;
                dp[i+mxN]=max((ll)dp[i+mxN], solv(i+mxN+ele.fir, wid, ele.fir)-(i+mxN)/(-ele.fir));
                //for(int j=1;j<=min(ele.sec, (i-(L-nval))/(-ele.fir));j++)  dp[i+mxN]=max(dp[i+mxN], dp[i+mxN+j*ele.fir]-j);
            }
        }
        if(ele.fir>0)
        {
            make_sps(ele.fir, 1);
            for(int i=L-nval;i<=M*M;i++)
            {
                int wid=min(ele.sec, (M*M-i)/ele.fir);
                if(wid==0)  continue;
                dp[i+mxN]=max((ll)dp[i+mxN], solv(i+mxN+ele.fir*wid, wid, ele.fir)+(i+mxN)/ele.fir);
                //for(int j=1;j<=min(ele.sec, (M*M-i)/ele.fir);j++)    dp[i+mxN]=max(dp[i+mxN], dp[i+mxN+j*ele.fir]-j);
            }
        }
    }
    if(dp[L-nval+mxN]<-MOD/10)    cout << "impossible";
    else    cout << ncnt+dp[L-nval+mxN]+A[mxN];
}
/*
2 2
0 0 0 0 1
*/

컴파일 시 표준 에러 (stderr) 메시지

vault.cpp: In function 'void make_sps(int, int)':
vault.cpp:28:87: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   28 |             if(j-(1<<i)*jump>=L-nval)   sps[j+mxN][i]=max(sps[j+mxN][i-1], sps[j-(1<<i-1)*jump+mxN][i-1]);
      |                                                                                      ~^~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3-1: 10 / 10
• Subtask 3-2: 0 / 10
• Subtask 4-1: 10 / 10
• Subtask 4-2: 0 / 10
• Subtask 5-1: 10 / 10
• Subtask 5-2: 0 / 10
• Subtask 6-1: 10 / 10
• Subtask 6-2: 0 / 10