| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1029285 | MDario | The short shank; Redemption (BOI21_prison) | C++11 | 0 ms | 0 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>
#include <vector>
using namespace std;
#define F first
#define S second
typedef long long ll;
const string noyes[2] = {"NO", "YES"};
const ll INFLL = (1ll << 62);
const int INF = (1 << 30);
const int MAXN = 300'000;
const ll MOD = 1'000'000'007;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n, D, T;
cin >> n >> D >> T;
ll a[n];
for (int i = 0; i < n; i++)
cin >> a[i];
ll pref[n];
{
ll c = 0;
ll last = INF;
for (int i = 0; i < n; i++) {
last = min(last + 1, a[i]);
if (last <= T) {
c++;
}
pref[i] = c;
// cout << c << " ";
}
// cout << "\n";
}
ll suf[n];
{
stack<ll> slow;
ll c = 0;
ll last = INF;
for (int i = n - 1; i >= 0; i--) {
last = a[i];
slow.push(i);
while (!slow.empty() && abs(i - slow.top()) + last <= T) {
c++;
slow.pop();
}
suf[i] = c;
}
// for (int i = 0; i < n; i++)
// cout << suf[i] << " ";
// cout << "\n";
}
ll ans = n;
for (int i = 0; i + 1 < n; i++)
ans = min(ans, pref[i] + suf[i + 1]);
cout << ans << "\n";
return 0;
}