Submission #708619

#	Time	Username	Problem	Language	Result	Execution time	Memory
708619		joelgun14	Stove (JOI18_stove)	C++17	100 / 100	53 ms	3196 KiB

stove

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
int main() {
    // alien trick
    int n, k;
    cin >> n >> k;
    int a[n + 1];
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    a[0] = a[1];
    // consider cost as dp[i]
    // maintain the minimum amount to achieve the desired minimum cost
    // dp[i] = min(dp[j] + cost(j, i) - penalty)
    int lb = 0, rb = 1e9, ans = -1;
    while(lb <= rb) {
        int mb = (lb + rb) / 2;
        // maintain rolling aja harusnya bs, tapi agk tricky karena ada shiftnya
        // actually tinggal maintain posisi T aja as negative
        pair<ll, int> curm = {-a[1], 0};
        pair<ll, int> dp[n + 1];
        //cout << mb << endl;
        for(int i = 1; i <= n; ++i) {
            dp[i] = {curm.fi + a[i] + mb + 1, curm.se + 1};
            //cout << "OUTPUT" << endl;
            //cout << curm.fi << " "<< a[i] << " " << mb << endl;
            //cout << curm.fi << " " << curm.se << " " << dp[i].fi - a[i] << " " << dp[i].se << endl;
            curm = min(curm, {dp[i].fi - a[i + 1], dp[i].se});
        }
        if(dp[n].se <= k) {
            // tambah penalti -> less k
            ans = mb;
            rb = mb - 1;
        }
        else
            lb = mb + 1;
    }
    pair<ll, int> curm = {-a[1], 0};
    pair<ll, int> dp[n + 1];
    //cout << ans << endl;
    for(int i = 1; i <= n; ++i) {
        dp[i] = {curm.fi + a[i] + ans + 1, curm.se + 1};
        //cout << i << endl;
        //cout << i << " " << dp[i].fi << " " << dp[i].se << endl;
        //cout << curm.fi << " " << curm.se << " " << dp[i].fi - a[i] << " " << dp[i].se << endl;
        curm = min(curm, {dp[i].fi - a[i + 1], dp[i].se});
    }
    ll res = dp[n].fi;
    //cout << res << " ";
    res -= 1ll * k * ans;
    cout << res << endl;
}

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