Submission #985470

#	Time	Username	Problem	Language	Result	Execution time	Memory
985470		AdamGS	Ski 2 (JOI24_ski2)	C++17	100 / 100	161 ms	334212 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e18+7;
const int LIM=307;
ll dp[LIM][LIM][LIM], odw[LIM][LIM][LIM], n, k;
pair<ll,ll>T[LIM];
vector<ll>P, ile, pref;
ll solve(ll a, ll b, ll c) {
  if(a==P.size()) return 0;
  b+=ile[a];
  if(odw[a][b][c]) return dp[a][b][c];
  odw[a][b][c]=1;
  if(b<=c) return dp[a][b][c]=solve(a+1, 0, c);
  return dp[a][b][c]=min(solve(a, b-ile[a], c+1)+pref[a-1], solve(a+1, b-c, c)+k*(b-c));
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n >> k;
  rep(i, n) cin >> T[i].st >> T[i].nd;
  sort(T, T+n);
  P.pb(-1);
  ll akt=-1;
  rep(i, n) {
    akt=max(akt+1, T[i].st);
    P.pb(akt);
  }
  rep(i, P.size()) {
    ile.pb(0);
    pref.pb(INF);
  }
  rep(i, n) {
    rep(j, P.size()) if(T[i].st==P[j]) {
      ++ile[j];
      pref[j]=min(pref[j], T[i].nd);
    }
  }
  rep(i, (int)P.size()-1) pref[i+1]=min(pref[i+1], pref[i]);
  cout << solve(0, 0, 1) << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'll solve(ll, ll, ll)':
Main.cpp:16:7: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   if(a==P.size()) return 0;
      |      ~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
Main.cpp:34:3: note: in expansion of macro 'rep'
   34 |   rep(i, P.size()) {
      |   ^~~
Main.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
Main.cpp:39:5: note: in expansion of macro 'rep'
   39 |     rep(j, P.size()) if(T[i].st==P[j]) {
      |     ^~~

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