제출 #1161617

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161617		vijcode	Rabbit Carrot (LMIO19_triusis)	C++20	0 / 100	1 ms	328 KiB

triusis

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

#define int long long

void printvec(vector<int> &vec){
    int n = vec.size();
    for(int i = 0; i < n; i++){
        cout << vec[i] << " ";
    }
    cout << endl;
}

signed main(){
    // freopen("cowjog.in", "r", stdin);
    // freopen("cowjog.out", "w", stdout);

    int n, m;
    cin >> n >> m;

    vector<int> h(n);
    for(int i = 0; i < n; i++) cin >> h[i];

    //dp[i] = minimum number of modifications needed to reach first i blocks;
    vector<int> dp(n+2, 0);
    if(h[0] <= m){
        dp[0] = 0;
    }
    else{
        dp[0] = 1;
        h[0] = m;
    }

    for(int i = 1; i < n; i++){
        int ch = h[i];
        int ph = h[i-1];
        int gap = ch - ph;
        if(gap <= m){
            dp[i] = dp[i-1];
        }
        else{
            // i-1 to 0
            //find modification needed
            //dp[i] = modifications needed
            int last = h[i];
            int mods = 0;
            // for(int j = i-1; j >= 0; j--){
            //     if(j==0){
            //         mods += dp[0];
            //         break;
            //     }

            //     int prevgap = last - h[j];
            //     if(prevgap > m){
            //         mods++;
            //         last = last - m;
            //     }
            //     else{
            //         last = h[j];
            //     }
            // }
            // dp[i] = mods;
            dp[i] = dp[i-1] + 1;
            h[i] = ph + m;
        }
    }

    cout << dp[n-1] << endl;

}

/*
5 400
300
700
200
1000
500

3 300
700
1000
1300
*/

• Subtask 1: 0 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 28
• Subtask 4: 0 / 37