Submission #1241652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241652		lambd47	Ski 2 (JOI24_ski2)	C++20	0 / 100	146 ms	213908 KiB

Main

#include <bits/stdc++.h>

#define int long long
using namespace std;

#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)

std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

const int MOD=1e18;
const int MX=301;
void solve() {
    int dp[MX][MX][MX];//guarda aonde eu to,ultima base de subir que peguei e quantos ta no bolso
    int n,m;cin>>n>>m;
    L(i,0,n){
        L(j,0,n){
            L(k,0,n){
                dp[i][j][k]=MOD;
            }
        }
    }
    vector<int> h(n);
    vector<int> c(n);
    vector<int> ord(n);iota(all(ord),0);
    L(i,0,n-1){
        cin>>h[i]>>c[i];
    }
    sort(all(ord),[&](int a, int b){
            if(h[a]==h[b])return c[a]>c[b];
            return h[a]<h[b];
    });
    vector<int> aux(n);
    L(i,0,n-1)aux[i]=h[ord[i]];
    h=aux;
    L(i,0,n-1)aux[i]=c[ord[i]];
    c=aux;

    vector<bool> pode(n,0);
    pode[n-1]=1;
    L(i,0,n-2){
        if(h[i]!=h[i+1])pode[i]=1;//pode virar uma base de subida
    }
    dp[n][n][0]=0;
    int resp=MOD;
    R(i,n-1,0){
        L(j,i+1,n){//ultima base
            L(k,0,n-1-i){
                dp[i][j][k+1]=min(dp[i][j][k+1],dp[i+1][j][k]);//so boto pra esperar
                if(pode[i]){
                    dp[i][j][1]=min(dp[i][j][1],dp[i+1][j][k]+k*c[i]);//esvazio os acumulados pro meu atual
                }
                if(pode[i])dp[i][i][k+1]=min(dp[i][i][k+1],dp[i+1][j][k]);//transformo em base de subida
                if(pode[i]){//posso esvaziar na base de subida tbm
                    dp[i][i][1]=min(dp[i][i][1],dp[i+1][j][k] +k*c[i]);
                }
                if(j!=n)dp[i][j][k]=min(dp[i][j][k],dp[i+1][j][k]+(h[j]-h[i]+1)*m + c[j]);//levo pra base de subida
            }
        }
    }//resp eh min dp[0][j][0]-c[j];

    int somat=0;
    L(i,0,n-1){
        L(j,i,n-1){
            resp=min(resp,-c[i]+dp[i][j][1]+(h[j]*i-somat+i)*m + c[j]*i);
        }
        somat+=h[i];
    }
    cout<<resp;




}
 
int32_t main() {
    std::cin.tie(0)->sync_with_stdio(0); 
    std::cin.exceptions(std::cin.failbit);

    int T = 1;
//    std::cin >> T;
    while(T--) {
        solve();
    }

	return 0;
}

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