Submission #1247862

#TimeUsernameProblemLanguageResultExecution timeMemory
1247862vlomaczkStove (JOI18_stove)C++20
0 / 100
1 ms324 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> typedef long long ll; using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, k; cin >> n >> k; vector<ll> T(n+1); for(int i=1; i<=n; ++i) cin >> T[i]; ll inf = 1e15; vector<pair<ll, ll>> dp(n+1, pair<ll, ll>({inf, 0})); ll start = -inf; ll koniec = inf; ll wynik = 0; while(start+1<koniec) { int alpha = (start+koniec)/2; dp[1] = {1-alpha, 1}; for(int i=2; i<=n; ++i) { int d = T[i]-T[i-1]; dp[i] = dp[i-1]; if(dp[i].first+1-alpha < dp[i].first + d) { dp[i].first += 1-alpha; dp[i].second++; } else { dp[i].first += d; } } int z = dp[n].second; wynik = dp[n].first + z*alpha; //cout << z << "\n"; //for(auto[a, b] : dp) cout << a << " " << b << "\n"; if(z==k) break; if(z > k) koniec = alpha; else start = alpha; } cout << wynik << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...