oj.uz

답안 #498970

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
498970 2021-12-26T21:00:29 Z Karabasan 구경하기 (JOI13_watching) C++17
0 / 100
 128 ms 64160 KB 
#include <bits/stdc++.h>
#define ll long long
#define fast1 ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4")
#pragma GCC optimize("unroll-loops")

ll n,m,ar[2005],p,q;
ll dp[2005][2005];
bool check(int w)
{
	int lp=0,lq=0;
	memset(dp,0,sizeof(dp));
	for(ll i=1;i<=n;i++)
	{
		while(ar[lp+1]<=ar[i]-w)
			lp++;

		while(ar[lq+1]<=ar[i]-2*w)
			lq++;

		for(int j=0;j<=min(i,p);j++)
		{
			if(j==0)
			{
				dp[i][j]=dp[lq][0]+1;
				continue;
			}
			int t1=dp[lp][j-1];
			int t2=dp[lq][j]+1;

			dp[i][j]=min(t1,t2);
		}
	}
	if(dp[n][min(n,p)]>q)
		return false;
	return true;
}

int main()
{
	fast1;
	cin>>n>>p>>q;
	for(int i=1;i<=n;i++)
		cin>>ar[i];
	sort(ar+1,ar+n+1);
	int bas=0;
	int son=1e9;
	while(bas<son)
    {
        int orta=(bas+son)/2;
        if(check(orta))
            son=orta;
        else bas=orta+1;
    }
    cout<<bas;
}

Subtask #1
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 31680 KB Output is correct
2 Runtime error 128 ms 64160 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 106 ms 31764 KB Output is correct
2 Runtime error 127 ms 64148 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -