Submission #1279355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279355		dl_nguyenducdung2k8	Stove (JOI18_stove)	C++20	100 / 100	20 ms	35616 KiB

stove

#include<bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

template<class X, class Y>bool maximize(X &x, const Y &y){if(x < y) return x = y, true; return false;}
template<class X, class Y>bool minimize(X &x, const Y &y){if(x > y) return x = y, true; return false;}

#define ll long long
#define fi first
#define se second
#define pb push_back
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for(int i = (b), _a = (a); i >= _a; i--)
#define REP(i, n) for(int i = 0, _n = (n); i < _n; i++)
#define C make_pair
#define MASK(i) (1LL << (i))
#define TURN_ON(i, x) ((x) | MASK(i))
#define TURN_OFF(i, x) ((x) & ~MASK(i))
#define CNT(x) (__builtin_popcountll(x))
#define get_bit(i, x) ((x) & MASK(i))
#define REV(i, x) ((x) ^ MASK(i))

const ll mod = 1e9 + 7;
const int INF = 2e9;
const int maxn = 1e5 + 5;
typedef pair<int, int> pi;
typedef pair<int, pair<int,int>> pii;
typedef pair<ll, ll> pl;
typedef pair<ll, pair<ll,ll>>pll;

const int MAXN = (int)1e5 + 5;

int n, k, t[MAXN];

void nhap(){
    cin >> n >> k;
    FOR(i, 1, n) cin >> t[i];
}
namespace sub1{
    vector<vector<int>>dp;

    bool check(){
        return n <= (int)5e3;
    }
    void solve(){
        dp.resize(n + 1, vector<int>(k + 1, +INF));
        dp[0][0] = 0;
        FOR(i, 1, n) FOR(j, 1, min(i, k)){
            dp[i][j] = min(dp[i - 1][j] + (t[i] - t[i - 1]), dp[i - 1][j - 1] + 1);
        }
        cout << dp[n][k];
    }
}
namespace sub2{
    vector<int>List;
    ll ans;

    void solve(){
        FOR(i, 1, n - 1) List.pb(t[i + 1] - t[i]), ans += (t[i + 1] - t[i]);
        sort(List.begin(), List.end(), greater<int>());
        REP(i, k - 1) ans = ans - List[i] + 1;
        cout << ans + 1;
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    nhap();
    if(sub1::check()) return sub1::solve(), 0;
    sub2::solve();
    return 0;
}

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