Submission #874240

#TimeUsernameProblemLanguageResultExecution timeMemory
874240tsumondaiStove (JOI18_stove)C++14
100 / 100
16 ms3312 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define pb push_back #define mp make_pair #define foru(i, l, r) for(int i = l; i <= r; i++) #define ford(i, r, l) for(int i = r; i >= l; i--) #define __TIME (1.0 * clock() / CLOCKS_PER_SEC) typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef pair<ii, ii> iiii; const int N = 1e5 + 5; const int oo = 1e18, mod = 1e9 + 7; int n, m, k, t[N]; string s; vector<int> dist; /* sieu tom tat: dươc phep chon toi da k diem sao cho tong cua cac khoang cach o cac diuem khong duoc chon la no nhat liet ke ra k cac khoang cach giua 1 dong diem day sort =))) ok let's try subtask 1: bitmask O(2^20) subtask 2: dp (N*N) subtask 3: greedy hoac la dp with data structure gi day */ void process() { int res=t[n]-t[1]+1; //cout << res << '\n'; foru(i,2,n) dist.pb(t[i]-t[i-1]); sort(dist.begin(), dist.end(), greater<int>()); /*for (auto x: dist) cout << x << ' '; cout << '\n';*/ foru(i,0,k-2) res-=(dist[i]-1); cout << res; return; } signed main() { cin.tie(0)->sync_with_stdio(false); //freopen(".inp", "r", stdin); //freopen(".out", "w", stdout); cin >> n >> k; foru(i,1,n) cin >> t[i]; process(); cerr << "Time elapsed: " << __TIME << " s.\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...