oj.uz

Submission #465146

# Submission time Handle Problem Language Result Execution time Memory
465146 2021-08-15T09:03:47 Z MahdiBahramian The short shank; Redemption (BOI21_prison) C++17
0 / 100
 1 ms 352 KB 
#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;
int n , t;
int A[Max];
long double dp[Max]; int last[Max] , cnt[Max];
void CALC(long double 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;
	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 += 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];

	long double l = 1e9 , r = -1e9;
	for(int lg = 0 ; lg < 100 ; lg++)
	{
		long double md = (l + r) / 2;
		CALC(md);
		if(cnt[n] > d) r = md;
		else l = md;
	}
	CALC(l);
	cout << (dp[n] - l * cnt[n]);
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -