Submission #524487

#TimeUsernameProblemLanguageResultExecution timeMemory
524487cqtshadowStove (JOI18_stove)C++14
100 / 100
161 ms196420 KiB
#include <bits/stdc++.h> #define MASK(x) (1LL << x) #define GETBIT(mask, x) ((mask >> (x))&1) #define ONBIT(mask, x) (mask | (1LL << (x))) #define Each(type, i, a, b) for(type i = (a) ; i <= (b) ; ++i) #define REach(type, i, a, b) for(type i = (a) ; i >= (b) ; --i) using namespace std; typedef long long ll; const int N = 1e5 + 7; const int MOD = 1e9 + 7; const int INF = 1e9; const double eps = 1e-9; const ll oo = 4e18; template<class X> bool maximize(X &x, X y) {return (x + eps < y ? x = y, true : false);} template<class X> bool minimize(X &x, X y) {return (x > y + eps ? x = y, true : false);} void add(int &x, int y) {x += y; if(x >= MOD) x -= MOD;} void sub(int &x, int y) {x -= y; if(x < 0) x += MOD;} int radd(int x, int y) {add(x, y); return x;} int rsub(int x, int y) {sub(x, y); return x;} string to2(int val) {bitset<10> temp(val); return temp.to_string();} int n, k; int t[N]; namespace SUB1 { int f[21][21]; int dp(int pos, int cnt) { if(pos > n) return 0; if(cnt >= k) return INF; int &res = f[pos][cnt]; if(res != -1) return res; res = INF; Each(int, i, pos, n) minimize(res, dp(i + 1, cnt + 1) + t[i] + 1 - t[pos]); return res; } void solve() { memset(f, -1, sizeof f); cout << dp(1, 0); exit(0); } } namespace SUB2 { ll f[5001][5001]; ll dp(int pos, int cnt) { if(pos > n) return 0; ll &res = f[pos][cnt]; if(res != -1) return res; res = dp(pos + 1, cnt) + t[pos] - t[pos - 1]; if(cnt + 1 <= k) minimize(res, dp(pos + 1, cnt + 1) + 1); return res; } void solve() { memset(f, -1, sizeof f); cout << dp(2, 1) + 1; exit(0); } } namespace SUB3 { int a[N]; void solve() { Each(int, i, 1, n - 1) a[i] = t[i + 1] - t[i]; ll ans = t[n] - t[1] + k; sort(a + 1, a + n, greater<int>()); Each(int, i, 1, k - 1) ans -= a[i]; cout << ans; } } int main() { // #ifndef ONLINE_JUDGE // freopen("JOI18_stove.inp", "r", stdin); // freopen("JOI18_stove.out", "w", stdout); // #endif ios::sync_with_stdio(false);cin.tie(nullptr); cin >> n >> k; Each(int, i, 1, n) cin >> t[i]; if(n <= 20) SUB1::solve(); if(n <= 5000) SUB2::solve(); SUB3::solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...