Submission #1120463

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120463		vjudge1	Uplifting Excursion (BOI22_vault)	C++17	5 / 100	5061 ms	395528 KiB

vault

// Bolatulu
#include <bits/stdc++.h>
// #include <art.h>

/*
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
*/

typedef long long ll;
typedef unsigned long long ull; 
typedef double db;
#define pb push_back
#define eb emplace_back
#define ins insert
#define F first
#define S second
#define md (tl+tr)/2
#define TL v+v,tl,md
#define TR v+v+1,md+1,tr
#define Tl t[v].l,tl,md
#define Tr t[v].r,md+1,tr
#define all(x) (x).begin(),(x).end()
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define int long long
// #define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);
using namespace std;

int binpow(int a,int n,int M) {
    if (n==0)
        return 1;
    if (n%2!=0)
        return (a * binpow(a,n-1,M))%M;
    int z=binpow(a,n/2,M);
    return (z*z)%M;
}

const ll INF = 1e18+7;
const int N = 5e3+7;

int m,l,a[N],b[N],dp[103][500007];

void solve() {
    cin >> m >> l;
    int s=0,ans;
    for (int i=m;i>=1;i--) {
        cin >> b[i];
        s-=b[i]*i;
    }
    cin >> ans;
    for (int i=1;i<=m;i++) {
        cin >> a[i];
        s+=a[i]*i;
        ans+=a[i]+b[i];
    }
    s-=l;
    int x=5e5+7;
    for (int i=m;i>=1 and abs(s)>=x;i--) {
        int z;
        if (s>0) {
            z=min((s-x)/i+1,a[i]);
            a[i]-=z;
            ans-=z;
            s-=z*i;
        } else {
            z=min((x-s)/i+1,b[i]);
            b[i]-=z;
            ans-=z;
            s+=z*i;
        }
    }
    if (abs(s)>=x) {
        cout << "impossible";
        return;
    }
    for (int i=0;i<=x;i++)
        dp[0][i]=INF;
    dp[0][abs(s)]=0;
    if (s<0) {
        for (int i=1;i<=m;i++)
            swap(a[i],b[i]);
    }
    for (int i=1;i<=m;i++) {
        for (int j=0;j<=x;j++) {
            dp[i][j]=INF;
            for (int k=0;k<=a[i] and j+k*i<=x;k++)
                dp[i][j]=min(dp[i-1][j+k*i]+k,dp[i][j]);
            for (int k=0;k<=b[i] and j-k*i>=0;k++)
                dp[i][j]=min(dp[i-1][j-k*i]+k,dp[i][j]);
        }
    }
    if (dp[m][0]==INF)
        cout << "impossible";
    else
        cout << ans-dp[m][0];
}   

signed main() {
    // file("jenga");
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int test = 1;
    // cin >> test;
    while (test--) {
        solve();
        if (test)
            cout << '\n';
    }
    return 0;
}

Compilation message (stderr)

vault.cpp: In function 'void solve()':
vault.cpp:79:17: warning: iteration 500007 invokes undefined behavior [-Waggressive-loop-optimizations]
   79 |         dp[0][i]=INF;
      |         ~~~~~~~~^~~~
vault.cpp:78:19: note: within this loop
   78 |     for (int i=0;i<=x;i++)
      |                  ~^~~
vault.cpp:87:21: warning: iteration 500007 invokes undefined behavior [-Waggressive-loop-optimizations]
   87 |             dp[i][j]=INF;
      |             ~~~~~~~~^~~~
vault.cpp:86:23: note: within this loop
   86 |         for (int j=0;j<=x;j++) {
      |                      ~^~~

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