Submission #1085325

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1085325	2024-09-08T00:57:20 Z	4QT0R	Watching (JOI13_watching)	C++17	100 / 100	128 ms	31868 KB

watching

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

ll eve[2003];
ll prv[2003];
ll prvdab[2003];
ll dp[2003][2003];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	ll n,p,q;
	cin >> n >> p >> q;
	for (ll i = 1; i<=n; i++)cin >> eve[i];
	sort(eve+1,eve+n+1);
	ll l=1,r=1e9,md;
	eve[0]=-1e9;
	while(l<r){
		md=(l+r)/2;
		ll iter=n;
		for (ll i = n; i>=1; i--){
			while(eve[i]-eve[iter]+1<=md)iter--;
			prv[i]=iter;
		}
		iter=n;
		for (ll i = n; i>=1; i--){
			while(eve[i]-eve[iter]+1<=2*md)iter--;
			prvdab[i]=iter;
		}
		for (ll i = 1; i<=n; i++){
			dp[i][0]=1+dp[prvdab[i]][0];
			for (ll j = 1; j<=min(n,p); j++){
				dp[i][j]=min(dp[prv[i]][j-1],1+dp[prvdab[i]][j]);
			}
		}
		bool ok=false;
		for (ll i = 1; i<=min(n,p); i++)if (dp[n][i]<=q)ok=true;
		if (ok)r=md;
		else l=md+1;
	}
	cout << l << '\n';
}

Subtask #1

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	860 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	860 KB	Output is correct
5	Correct	0 ms	860 KB	Output is correct
6	Correct	1 ms	856 KB	Output is correct
7	Correct	1 ms	748 KB	Output is correct
8	Correct	1 ms	860 KB	Output is correct
9	Correct	0 ms	860 KB	Output is correct
10	Correct	0 ms	860 KB	Output is correct
11	Correct	1 ms	716 KB	Output is correct
12	Correct	1 ms	860 KB	Output is correct
13	Correct	1 ms	860 KB	Output is correct
14	Correct	0 ms	860 KB	Output is correct
15	Correct	1 ms	860 KB	Output is correct

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	8540 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	93 ms	31708 KB	Output is correct
4	Correct	122 ms	31832 KB	Output is correct
5	Correct	9 ms	9560 KB	Output is correct
6	Correct	128 ms	31836 KB	Output is correct
7	Correct	5 ms	9048 KB	Output is correct
8	Correct	12 ms	10332 KB	Output is correct
9	Correct	46 ms	20128 KB	Output is correct
10	Correct	121 ms	31868 KB	Output is correct
11	Correct	9 ms	9820 KB	Output is correct
12	Correct	58 ms	23780 KB	Output is correct
13	Correct	5 ms	8792 KB	Output is correct
14	Correct	5 ms	8796 KB	Output is correct
15	Correct	4 ms	8796 KB	Output is correct