Submission #1247779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247779		chaeryeong	Ski 2 (JOI24_ski2)	C++20	0 / 100	147 ms	337788 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[81][81][81][81];
vector <int> heights[81];
int n, k, h[41],c[41];
vector <int> dist;
int ans (int w,int x,int y, int z){
if(w==81){
if(x==0)return 0;
return 1e18;
}
int &ret=dp[w][x][y][z];
if(ret !=-1)return ret;
ret=1e18;
auto g = heights[w];
for(int i=1;i<=x;i++)g.push_back(dist.size()-1);
ret = min(ret, ans(w+1,g.size(),y,z)+k*(int)g.size());
if(y==0){
ret=min(ret,ans(w+1,g.size()-1,1,g[0])+k*((int)g.size()-1));
return ret;
}
for(int i=0;i<g.size();i++){
ret=min(ret,ans(w+1,g.size()-i-1,max(0ll,y-(i+1))+i+1,min(g[0],z))+dist[z]*max(0ll,i+1-y)+k*((int)g.size()-1-i));
}
return ret;
}
signed main (){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>h[i]>>c[i];
dist.push_back(c[i]);
}
dist.push_back(1e18);
sort(dist.begin(),dist.end());
dist.resize(unique(dist.begin(),dist.end())-dist.begin());
for(int i=1;i<=n;i++){
int x=lower_bound(dist.begin(),dist.end(),c[i])-dist.begin();
heights[h[i]].push_back(x);
}
for (int i=0;i<=40;i++){
sort(heights[i].begin(),heights[i].end());
}
memset(dp,-1,sizeof(dp));
cout<<ans(0,0,0,dist.size()-1)<<endl;
}

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