Submission #1110867

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110867		salmon	Ski 2 (JOI24_ski2)	C++14	100 / 100	279 ms	311636 KiB

Main

#include <bits/stdc++.h>
using namespace std;

int N, K, H;
long long int memo[400][400][400];
vector<pair<int,int>> v;
int h,h1;
vector<int> vh;
int cost[400];
const int inf = 1.1e9;
int sise[400];

int main(){

    scanf(" %d",&N);
    scanf(" %d",&K);

    for(int i = 0; i < N; i++){
        scanf(" %d",&h);
        scanf(" %d",&h1);

        v.push_back({h,h1});
    }

    sort(v.begin(),v.end());

    int p = -1;

    for(int i = 0; i < N; i++){
        if(v[i].first <= p){
            p++;
            vh.push_back(p);
        }
        else{
            p = v[i].first;
            vh.push_back(p);
        }
    }


    H = vh.size();

    cost[0] = inf;
    sise[0] = 0;

    auto it = 0;
    for(int i = 0; i < N; i++){
        while(vh[it] != v[i].first){
            it++;
            cost[it] = cost[it - 1];
            sise[it] = 0;
        }
        cost[it] = min(cost[it], v[i].second);
        sise[it]++;
    }

    while(it != H - 1){
        it++;
        cost[it] = cost[it - 1];
        sise[it] = 0;
    }

    for(int i = 0; i < H; i++){
        for(int j = 0; j <= N; j++){
            for(int k = 0; k <= N; k++){
                memo[i][j][k] = -1;
            }
        }
    }

    for(int i = H - 1; i >= 0; i--){
        if(i != H - 1){

        }

        long long int pre[N + 1][N + 1];
        if(i != 0 && i != H - 1){
            for(int j = 0; j <= N; j++){
                for(int k = 1; k <= N; k++){
                    pre[j][k] = memo[i + 1][j][k] + j * (long long int)K;
                }
            }

            for(int j = 1; j <= N; j++){
                for(int k = 1; k <= N; k++){
                    if(k != N) pre[j][k] = min(pre[j - 1][k + 1] + cost[i - 1], pre[j][k]);
                }
            }
        }

        for(int j = 0; j <= N; j++){
            for(int k = 1; k <= N; k++){
                if(i == H - 1){
                    memo[i][j][k] = max(0,(j + sise[i] - k)) * (long long int)cost[i - 1];
                }
                else if(i == 0){
                    int num = max(0, j + sise[i] - k);

                    memo[i][j][k] = inf * (long long int)inf;

                    if(memo[i + 1][num][k] != -1){
                        memo[i][j][k] = min(memo[i][j][k], memo[i + 1][num][k] + num * (long long int)K);
                    }
                }
                else{
                    int num = max(0, j + sise[i] - k);

                    if(num > N) memo[i][j][k] = inf * (long long int) inf;
                    else memo[i][j][k] = pre[num][k];
                }
                //printf("%lld ",memo[i][j][k]);
            }
            //printf("\n");
        }
        //printf("\n");
    }

    printf("%lld",memo[0][0][1]);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
Main.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf(" %d",&K);
      |     ~~~~~^~~~~~~~~~
Main.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         scanf(" %d",&h);
      |         ~~~~~^~~~~~~~~~
Main.cpp:20:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         scanf(" %d",&h1);
      |         ~~~~~^~~~~~~~~~~

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