Submission #1008518

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008518		GrindMachine	Ski 2 (JOI24_ski2)	C++17	86 / 100	1469 ms	1048576 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

/*

knew beforehand that it was dp

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

void solve(int test_case)
{
    ll n,k; cin >> n >> k;
    vector<pll> a(n+5);
    rep1(i,n) cin >> a[i].ff >> a[i].ss;
    sort(a.begin()+1,a.begin()+n+1);
    ll m = n+a[n].ff;

    ll ans = inf2;

    rep1(s,n){
        auto b = a;
        ll add_cost = 0;
        swap(b[s],b[1]);

        rep1(i,n){
            if(i == 1) conts;
            if(b[i].ff <= b[1].ff){
                ll add = b[1].ff-b[i].ff+1;
                b[i].ff += add;
                add_cost += add*k;
            }
        }

        sort(b.begin()+1,b.begin()+n+1);

        vector<pll> c,d;
        c.pb({0,0}), d.pb({0,0});
        ll mn = inf2;

        rep1(i,n){
            if(b[i].ss < mn){
                d.pb(b[i]);
                mn = b[i].ss;
            }
            else{
                c.pb(b[i]);
            }
        }

        d.pb({m+1,-1});

        ll siz1 = sz(c)-1, siz2 = sz(d)-1;
        ll dp[siz1+5][m+5][n+5];
        memset(dp,0x3f,sizeof dp);
        dp[1][d[1].ff][1] = 0;

        rep1(i,siz1){
            rep(h,m+1){
                ll mn_cost = inf2;
                ll nxth = inf2;
                rep1(j,siz2){
                    auto [height,cost] = d[j];
                    if(height > h){
                        amin(nxth,height);
                    }
                    else{
                        amin(mn_cost,cost);
                    }
                }

                // place from c[i]
                rep(f,n+1){
                    if(dp[i][h][f] > inf2) conts;

                    ll sumh = 0;

                    for(int j = i; j <= siz1; ++j){
                        sumh += c[j].ff;
                        ll h2 = max((ll)h+1,c[j].ff);
                        if(h2 > nxth) break;

                        ll curr_sum = sumh, curr_cnt = j-i+1;
                        if(h2 == nxth){
                            curr_sum += nxth;
                            curr_cnt++;
                        }

                        ll sub = min((ll)f,curr_cnt);
                        ll f2 = f-sub+curr_cnt;
                        ll curr_cost = (curr_cnt-sub)*mn_cost;
                        curr_cost += (curr_cnt*h2-curr_sum)*k;

                        // if(i == 1 and j == 2 and h == 0 and f == 1){
                        //     debug(mn_cost);
                        //     debug(curr_cnt);
                        //     debug(sumh);
                        //     debug(f2,h2);
                        // }

                        amin(dp[j+1][h2][f2],dp[i][h][f]+curr_cost);
                    }
                }

                // place from d[i] (nxth)
                if(nxth <= m){
                    rep(f,n+1){
                        ll f2 = f;
                        ll curr_cost = 0;
                        if(f2 == 0){
                            curr_cost += mn_cost;
                        }
                        else{
                            f2--;
                        }

                        f2++;
                        amin(dp[i][nxth][f2],dp[i][h][f]+curr_cost);
                    }
                }
            }
        }

        ll best = inf2;
        rep(h,m+5){
            rep(f,n+5){
                ll val = dp[siz1+1][h][f];
                amin(best,dp[siz1+1][h][f]);
            }
        }

        best += add_cost;
        amin(ans,best);

        break;
    }

    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve(int)':
Main.cpp:176:20: warning: unused variable 'val' [-Wunused-variable]
  176 |                 ll val = dp[siz1+1][h][f];
      |                    ^~~

• Subtask 1: 5 / 5
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 33 / 33
• Subtask 5: 27 / 27
• Subtask 6: 0 / 14