Submission #1012110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012110		huutuan	Ski 2 (JOI24_ski2)	C++14	100 / 100	467 ms	234064 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N=310, inf=1e18;
int n, z, f[N][N][N], c[N], cnt[N];
pair<int, int> a[N];
vector<int> vals;
int d[N];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> z;
   map<int, int> mp;
   for (int i=1; i<=n; ++i){
      cin >> a[i].first >> a[i].second;
      ++a[i].first;
      ++mp[a[i].first];
   }
   {
      int cur=0;
      for (auto it=mp.begin(); it!=mp.end(); ++it){
         int dist=it->first;
         if (it!=mp.begin()) dist-=prev(it)->first;
         cur=max(0ll, cur-dist)+it->second;
         for (int j=0; j<cur; ++j) vals.push_back(it->first+j);
      }
   }
   vals.push_back(0);
   sort(vals.begin(), vals.end()); vals.resize(unique(vals.begin(), vals.end())-vals.begin());
   assert((int)vals.size()<N);
   for (int i=1; i<=n; ++i) a[i].first=lower_bound(vals.begin(), vals.end(), a[i].first)-vals.begin(), ++cnt[a[i].first];
   for (int i=0; i<(int)vals.size()-1; ++i) d[i]=vals[i+1]-vals[i];
   for (int i=0; i<N; ++i) c[i]=inf;
   for (int i=1; i<=n; ++i) c[a[i].first+1]=min(c[a[i].first+1], a[i].second);
   for (int i=1; i<N; ++i) c[i]=min(c[i], c[i-1]);
   for (int i=0; i<N; ++i) for (int j=0; j<N; ++j) for (int k=0; k<N; ++k) f[i][j][k]=inf;
   f[0][1][0]=0;
   for (int i=0; i<N-1; ++i) for (int j=1; j<=n; ++j) for (int k=0; k<=n; ++k) if (f[i][j][k]!=inf){
      for (int x=min(cnt[i+1]+k, j); x<=cnt[i+1]+k; ++x){
         if (c[i+1]==inf && x-j>0) continue;
         f[i+1][max(j, x)][k+cnt[i+1]-x]=min(f[i+1][max(j, x)][k+cnt[i+1]-x], f[i][j][k]+max(0ll, x-j)*c[i+1]+(k+cnt[i+1]-x)*z*d[i+1]);
      }
   }
   int ans=inf;
   for (int i=0; i<=n; ++i) ans=min(ans, f[(int)vals.size()-1][i][0]);
   cout << ans << '\n';
   return 0;
}

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