이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ve vector
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9 + 10;
const ll LLINF = (ll)1e18 + 10;
int n, d, t;
ve<int> T;
pll calcDP(ll lambda) {
ve<pll> DP(n, {LLINF, -1});
DP[n - 1] = {0, 0};
for (int i = n - 2; i >= 0; i--) {
int z = INF;
int cnt = 0;
for (int j = i + 1; j < n; j++) {
if (T[j] <= t || z <= t) cnt++;
z = min(z, T[j]);
z++;
pll v = {DP[j].first + cnt - lambda, DP[j].second + 1};
DP[i] = min(DP[i], v);
}
}
pll ans = {LLINF, -1};
int z = INF;
int cnt = 0;
for (int i = 0; i < n; i++) {
if (T[i] <= t || z <= t) cnt++;
z = min(z, T[i]);
z++;
pll v = {DP[i].first + cnt, DP[i].second};
ans = min(ans, v);
}
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> d >> t;
T = ve<int>(n);
for (int i = 0; i < n; i++) {
cin >> T[i];
}
ll lo = 0;
ll hi = 2e6;
ll c, x;
while (lo != hi) {
ll mi = (lo + hi) / 2;
x = calcDP(mi).second;
if (x > d) lo = mi + 1;
else hi = mi;
}
tie(c, x) = calcDP(lo);
ll ans = c + x * lo;
cout << ans << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |