Submission #545453

#	Time	Username	Problem	Language	Result	Execution time	Memory
545453		pokmui9909	오렌지 출하 (JOI16_ho_t1)	C++17	100 / 100	50 ms	816 KiB

2016_ho_t1

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

ll N, M, K;
ll A[20005], D[20005];

int main(){
    cin.tie(0) -> sync_with_stdio(false);

    cin >> N >> M >> K;
    for(ll i = 1; i <= N; i++){
        cin >> A[i];
    }
    for(ll i = 1; i <= N; i++){
        D[i] = 1e18;
        ll x = A[i], y = A[i], c = 0;
        for(ll j = i; j >= max(1LL, i - M + 1); j--){
            x = min(x, A[j]), y = max(y, A[j]), c++;
            D[i] = min(D[i], D[j - 1] + K + c * (y - x));
        }
    }
    cout << D[N];
}

• Subtask 1: 20 / 20
• Subtask 2: 50 / 50
• Subtask 3: 30 / 30