# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1100930 | akzytr | Stove (JOI18_stove) | C++17 | 1079 ms | 10212 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
template <typename T> using ve = vector<T>;
template <typename T, int sz> using ar = array<T, sz>;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
#define endl '\n'
int main() {
int N, K;
cin >> N >> K;
ve<ll> times;
map<ll, ll> occ;
for(ll i = 0; i < N; i++) {
ll x;
cin >> x;
times.pb(x);
occ[x] = 1;
times.pb(x + 1);
}
sort(times.begin(), times.end());
times.erase(unique(times.begin(), times.end()), times.end());
ll dp[times.size() + 2][K+1][2];
for(ll i = 0; i < times.size(); i++) {
for(ll j = 0; j <= K; j++) {
dp[i][j][0] = (ll)1e18;
dp[i][j][1] = (ll)1e18;
}
}
for(ll i = times.size() - 1; i >= 0; i--) {
if(occ[times[i]]) {
break;
}
for(ll k = 0; k <= K; k++) {
dp[i][k][0] = 0;
}
}
for(ll i = times.size() - 1; i >= 0; i--) {
for(ll left = K; left >= 1; left--) {
// ON
if(occ[times[i]]) {
for(ll j = i + 1; j < times.size(); j++) {
dp[i][left][1] = min(dp[i][left][1], dp[j][left - 1][0] + times[j] - times[i]);
}
} else {
for(ll j = i + 1; j < times.size(); j++) {
if(occ[times[j]] == 1) {
dp[i][left][0] = min(dp[i][left][0], dp[j][left][1]);
break;
}
}
}
}
}
cout << min(dp[0][K][0], dp[0][K][1]) << endl;
}
/*
Subtask 1) N<=20 & Ti<=20
N * K * T greedy
DP[i][left][on] which means the stove is on on the i'th day
DP[i][left][off]
*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |