Submission #1271939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271939		arianshabaani	Stove (JOI18_stove)	C++20	50 / 100	223 ms	196736 KiB

stove

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

// #CONFIG
string outone = "SUCCESS";
string outtwo = "IMPOSSIBLE";

const int inf=1e9;
const int mod=1e9+7;
const int maxn25=2*1e5+10;
const int maxn55=5*1e5+10;
const int maxn5=1e5+10;
const int maxn7=1e7+10;
const int maxn9=1e9+10;

#define ll long long int
#define ull unsigned long long int
#define pass cerr << "Pass shod!" << endl
#define testc ll tt; cin >> tt; while(tt--)
#define pb push_back
#define mp(i, j) make_pair(i, j)
#define migmig cin.tie(0); cout.tie(0); ios::sync_with_stdio(false)
#define one first
#define two second
#define enld endl
#define neld endl
#define cosnt const
#define ppq priority_queue
#define rip return 0;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef priority_queue<pll, vector<pll>, greater<pll>> pq;

void yes() { cout << "YES" << endl; }
void no() { cout << "NO" << endl; }
void out1() { cout << outone << endl; }
void out2() { cout << outtwo << endl; }
ll max3 (ll a, ll b, ll c) { return max(a, max(b, c)); }
ll min3 (ll a, ll b, ll c) { return min(a, min(b, c)); }
ll ceill (ll a, ll b) { return (a+b-1)/b; }
long double flor(long double a){ return floor(a+0.5); }
ll logg (ll a, ll b) { return log(a)/log(b); }

const int maxn = 5010;
int a[maxn];
ll dp[maxn][maxn];

int main(){
    migmig;
    int n, k;
    cin >> n >> k;
    for (int i=1; i<=n; i++){
        cin >> a[i];
        dp[i][0]=inf;
        for (int j=i+1; j<=n; j++){
            dp[i][j]=inf;
        }
    }
    dp[1][1]=1;
    for (int i=2; i<=n; i++){
        for (int j=1; j<=k; j++){
            dp[i][j]=min(dp[i-1][j]+(a[i]-a[i-1]), dp[i-1][j-1]+1);
        }
    }
    ll minn = INT_MAX;
    for (int i=1; i<=k; i++){
        minn=min(minn, dp[n][i]);
    }
    cout << minn << endl;
}

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