Submission #1031609

#TimeUsernameProblemLanguageResultExecution timeMemory
1031609PhuocStove (JOI18_stove)C++14
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> #include <iostream> #include <cmath> #include <iomanip> #include <vector> #include <map> #include <stack> #include <queue> using namespace std; #define ll long long #define pb push_back #define el '\n' #define mpair make_pair #define MASK(i) (1LL << (i)) #define BIT(mask, i) (((mask) >> (i)) & 1) #define fi first #define se second /* Author: Pham Gia Phuoc */ const int MOD = (int)(1e9) + 7; template <class T1, class T2> void add(T1 &a, T2 b){ a += b; if(a >= MOD) a -= MOD; } template <class T1, class T2> void sub(T1 &a, T2 b){ a -= b; if(a < 0) a += MOD; } template <class T1, class T2> bool minimize(T1 &a, T2 b){ if(a > b){a = b; return true;} return false; } template <class T1, class T2> bool maximize(T1 &a, T2 b){ if(a < b){a = b; return true;} return false; } /** END OF TEMPLATE. DRINK A CUP OF COFFEE BEFORE READING MY CODE **/ const int MAX = 100010; const ll INF = (ll) 1e18 + 67LL; const int oo = (int)(1e9 + 7); const int NUM_BIT = 62; int N, K, t[MAX]; void init(){ cin >> N >> K; for(int i = 1; i <= N; i++) cin >> t[i]; } bool checkSubtask1(){ if(N > 20) return false; for(int i = 1; i <= N; i++) if(t[i] > 20) return false; return true; } void solveSubtask1(){ ll ans = INF; for(int mask = 0; mask < MASK(N); mask++) if(__builtin_popcount(mask) <= K - 1) { ll cur = 0; int pre = 1; for(int i = 2; i <= N; i++) if(BIT(mask, i - 1)) { cur += (t[i - 1] + 1 - t[pre]); pre = i; } cur += (t[N] + 1 - t[pre]); minimize(ans, cur); } cout << ans << el; } void solveSubtask3(){ ll ans = t[N] - t[1] + 1; vector <ll> b; for(int i = 2; i < N; i++) b.push_back(1LL * (t[i + 1] - (t[i] + 1))); sort(b.begin(), b.end(), greater <ll>()); for(int i = 0; i < K - 1; i++){ ans -= b[i]; } cout << ans; } void solve(){ // if(checkSubtask1()){solveSubtask1(); return;} solveSubtask3(); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define test "test" int t = 1; while(t--){ init(); solve(); } return 0; } /*** ROAD TO VOI 2024 ***/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...