Submission #1175066

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175066		hiepsimauhong	Stove (JOI18_stove)	C++20	50 / 100	23 ms	47432 KiB

stove

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int64_t oo = 1e9;
//#define int long long

#define quickly ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define print(a,l,r) for(int OK(l); OK <= r ; ++OK){ if(a[OK] < oo){cout << a[OK] <<' ';} else{cout << "- ";}} cout << '\n';
#define prints(a) for(auto i : a){ cout << i <<' ';} cout << '\n';
#define printz(a,l,r) for(int OK(1) ; OK <= l ; ++OK){for(int KO(1) ; KO <= r ; ++KO){if(a[OK][KO] < oo){cout << a[OK][KO] <<' ';}else{cout << "- ";}}cout << '\n';} cout << '\n';
#define fs first
#define sd second
#define th second.second
#define ii pair<int,int>
#define iii pair<int, ii>
#define all(a) a.begin(), a.end()
const int N = 5000 + 5;
const int mod = 1e9 + 7;

int n, k;
int DP[N][N], a[N], pre[N];

signed main(){ quickly
        cin >> n >> k;

        for(int i(1) ; i <= n ; ++i){
                cin >> a[i];
                DP[0][i] = oo;
        }

        for(int i(1) ; i <= k ; ++i){
                int otp = 0;
                for(int r(1) ; r <= n ; ++r){
                        otp = min(otp, DP[i - 1][r - 1] - a[r]);
                        DP[i][r] = a[r] + otp + 1;
                }
        }
        cout << DP[k][n];
}

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