제출 #1156644

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1156644		guagua0407	Ski 2 (JOI24_ski2)	C++20	0 / 100	25 ms	4676 KiB

Main

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

const ll inf=(ll)1e18;
const int mxn=305;
vector<vector<ll>> dp(mxn,vector<ll>(mxn,inf));
vector<vector<ll>> mn(mxn,vector<ll>(mxn,inf));
vector<vector<ll>> mn2(mxn,vector<ll>(mxn,inf));

signed main() {_
    int n,K;
    cin>>n>>K;
    vector<int> c(n),h(n);
    vector<int> pre(mxn*2);
    for(int i=0;i<n;i++){
        cin>>h[i]>>c[i];
    }
    ll ans=0;
    int mnh=*min_element(all(h));
    ll mnc=inf;
    for(int i=0;i<n;i++){
        if(h[i]==mnh) mnc=min(mnc,c[i]);
    }
    int pos;
    for(int i=0;i<n;i++){
        if(h[i]==mnh and c[i]==mnc) pos=i;
    }
    for(int i=0;i<n;i++){
        if(h[i]==mnh and i!=pos){
            h[i]++;
            ans+=K;
        }
    }
    for(int i=0;i<n;i++){
        pre[h[i]]++;
    }
    for(int i=1;i<mxn*2;i++){
        pre[i]+=pre[i-1];
    }
    vector<vector<ll>> dpn(mxn,vector<ll>(mxn,inf));
    vector<vector<ll>> mnn(mxn,vector<ll>(mxn,inf));
    vector<vector<ll>> mn2n(mxn,vector<ll>(mxn,inf));
    ll mnans=inf;
    for(int i=0;i<5;i++){
        if(i==0){
            dpn[1][1]=0;
        }
        else{
            for(int j=0;j<=pre[i];j++){
                for(int k=0;k<=j;k++){
                    dpn[j][k]=min(mn[j-k][k]+k*mnc+(pre[i]-j)*K,mn2[j][k]+(pre[i]-j)*K);
                }
            }
        }
        for(int j=0;j<=n;j++){
            mnn[j][0]=dpn[j][0];
            for(int k=1;k<=n;k++){
                mnn[j][k]=min(dpn[j][k]-k*mnc,mnn[j][k-1]);
            }
        }
        for(int k=0;k<=n;k++){
            multiset<ll> S;
            for(int j=0;j<=n;j++){
                S.insert(dpn[j][k]);
                if(j-k-1>=0) S.erase(S.find(dpn[j-k-1][k]));
                mn2n[j][k]=*S.begin();
            }
        }
        for(int j=0;j<=n;j++){
            for(int k=0;k<=n;k++){
                dp[j][k]=dpn[j][k];
                mn[j][k]=mnn[j][k];
                mn2[j][k]=mn2n[j][k];
                dpn[j][k]=inf;
                mnn[j][k]=inf;
                mn2n[j][k]=inf;
                //cout<<i<<' '<<j<<' '<<k<<' '<<dp[j][k]<<'\n';
            }
        }
        for(int k=0;k<=n;k++){
            mnans=min(mnans,dp[n][k]);
        }
    }
    cout<<mnans+ans<<'\n';
    return 0;
}
//maybe its multiset not set
//yeeorz
//diaoborz
// dp(i-1,j,k)->dp(i,j+a,max(a,k))
// dp(i,j,k)=dp(i-1,j-k,k'<=k)+(k-k')*mn+(pre[i]-j)*k
// dp(i,j,k)=dp(i-1,j-(a<=k),k)+(pre[i]-j)*k

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

Main.cpp: In function 'void setIO(std::string)':
Main.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:17:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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