Submission #1184447

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184447		kl0989e	The short shank; Redemption (BOI21_prison)	C++17	0 / 100	4 ms	8260 KiB

prison

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

const int maxn=2e6+10;

vi a(maxn);
int n,d,t;

pi solve(long double price) {
	vector<vector<long double>> dp(n+1,vector<long double>(n+1,n));
	vector<vi> cnt(n+1,vi(n+1,0));
	dp[0][0]=0;
	for (int i=0; i<n; i++) {
		for (int j=0; j<=n; j++) {
			int jj=max(j,min(n,i+t-a[i]+1));
			if (dp[i+1][jj]>dp[i][j]+(j>i && a[i]>t)) {
				dp[i+1][jj]=dp[i][j]+(j>i && a[i]>t);
				cnt[i+1][jj]=cnt[i][j];
			}
			if (a[i]>t && dp[i+1][0]>dp[i][j]+price) { 
				dp[i+1][0]=dp[i][j]+price;
				cnt[i+1][0]=cnt[i][j]+1;
			}
		}
	}
	pi ans={1e9,1e9};
	for (int i=0; i<=n; i++) {
		pi temp={dp[n][i]-price*cnt[n][i],cnt[n][i]};
		ans=min(ans,temp);
	}
	return ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> d >> t;
	int cnt=0;
    for (int i=0; i<n; i++) {
        cin >> a[i];
		if (a[i]<=t) {
			cnt++;
		}
    }
	pi ans={n,n};
	long double l=0,r=n;
	for (int i=0; i<2+ceil(log2(n)); i++) {
		long double m=l+(r-l)/2;
		pi temp=solve(m);
		ans=min(ans,temp);
		if (temp.se>d) {
			l=m;
		}
		else {
			r=m;
		}
	}
	cout << ans.fi+cnt << '\n';
    return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20