Submission #465262

#	Time	Username	Problem	Language	Result	Execution time	Memory
465262		MahdiBahramian	The short shank; Redemption (BOI21_prison)	C++11	0 / 100	1 ms	332 KiB

prison

#include<bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define mk make_pair
#define mt make_tuple
using namespace std;
const int Max = 2e6 + 10 , INF = 1e9 + 10;
typedef double dbl;
int n , t;
int A[Max];
dbl dp[Max]; int last[Max] , cnt[Max];
void CALC(dbl tst)
{
	/*
	last[0] = INF;
	for(int i = 1 ; i <= n ; i++)
	{
		dp[i] = dp[i - 1] + tst + int(A[i] <= t);
		cnt[i] = cnt[i - 1] + 1;
		last[i] = A[i];

		if(dp[i] >= dp[i - 1] + int(min(last[i - 1] + 1 , A[i]) <= t))
		{
			dp[i] = dp[i - 1] + int(min(last[i - 1] + 1 , A[i]) <= t);
			cnt[i] = cnt[i - 1];
			last[i] = min(last[i - 1] + 1 , A[i]);
		}
	}
	*/
	cnt[0] = -1 , dp[0] = -tst;
	for(int i = 1 ; i <= n ; i++) dp[i] = 1e18 , cnt[i] = 0;
	for(int i = 0 ; i < n ; i++)
	{
		int lst = INF;
		int ct = 0;
		for(int j = i + 1 ; j <= n ; j++)
		{
			lst = min(lst + 1 , A[j]);
			ct += int(lst <= t);
			if(mk(dp[j] , cnt[j]) > mk(dp[i] + tst + ct , cnt[i] + 1))
			{
				dp[j] = dp[i] + tst + ct;
				cnt[j] = cnt[i] + 1;
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
	int d; cin >> n >> d >> t;
	for(int i = 1 ; i <= n ; i++) cin >> A[i];

	dbl l = 1e9 , r = -1e9;
	for(int lg = 0 ; lg < 100 ; lg++)
	{
		dbl md = (l + r) / 2.0;
		CALC(md);
		if(cnt[n] > d) r = md;
		else l = md;
	}
	CALC(l);
	//cout << 4 << '\n';
	cout << int(dp[n] - l * cnt[n] + 0.5) << '\n';
}

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