제출 #1012065

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1012065		huutuan	Ski 2 (JOI24_ski2)	C++14	0 / 100	2050 ms	233700 KiB

Main

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>

using namespace std;
using ll=long long;

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

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> z;
   for (int i=1; i<=n; ++i){
      cin >> a[i].first >> a[i].second;
      ++a[i].first;
      ++cnt[a[i].first];
   }
   for (int i=0; i<N; ++i) c[i]=1e9;
   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=0; j<=n; ++j) for (int k=0; k<=n; ++k) if (f[i][j][k]!=inf){
      for (int d=-cnt[i+1]; d<=k; ++d){
         int x=cnt[i+1]+d;
         f[i+1][max(j, x)][k-d]=min(f[i+1][max(j, x)][k-d], f[i][j][k]+1ll*max(0, x-j)*c[i+1]+1ll*(k-d)*z);
      }
   }
   ll ans=inf;
   for (int i=0; i<=n; ++i) ans=min(ans, f[N-1][i][0]);
   cout << ans << '\n';
   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