답안 #264827

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
264827	2020-08-14T10:21:49 Z	Goolakh	구경하기 (JOI13_watching)	C++17	100 / 100	199 ms	32120 KB

watching

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

#pragma GCC optimize("O2")

#define F first
#define S second
#define pb push_back
#define SZ(x) (ll)(x.size())
#define all(x) x.begin(),x.end()
#define MP make_pair

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=2e3+10, maxm=1e6+10, lg=10, mod=1e9+7, inf=1e18;

ll n,t1,t2,a[maxn],dp[maxn][maxn],nx1[maxn],nx2[maxn];
bool check(ll d){
	memset(dp,0,sizeof(dp));
	for(int i=0,p1=1,p2=1;i<n;i++){
		while(a[p1]-a[i]+1<=d) p1++;
		while(a[p2]-a[i]+1<=2*d) p2++;
		nx1[i]=p1, nx2[i]=p2;
		//if(d==4) cout<<i<<' '<<nx1[i]<<' '<<nx2[i]<<endl;
	}
	for(int i=0;i<=t1;i++)for(int j=0;j<=t2;j++){
		if(dp[i][j]>=n) return 1;
		dp[i+1][j]=max(dp[i+1][j],nx1[dp[i][j]]);
		dp[i][j+1]=max(dp[i][j+1],nx2[dp[i][j]]);
	}
	return 0;
}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	cin>>n>>t1>>t2;
	for(int i=0;i<n;i++) cin>>a[i];
	sort(a,a+n); a[n]=inf;
	//check(4);
	ll l=0,r=mod-7,mid;
	while(r-l>1){
		mid=(l+r)/2;
		if(check(mid)) r=mid;
		else           l=mid;
	}
	cout<<r;
	
	return 0;
}
// a denial a denial a denial a denial a denial a denial

Subtask #1

50.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	139 ms	32000 KB	Output is correct
2	Correct	141 ms	32000 KB	Output is correct
3	Correct	139 ms	32120 KB	Output is correct
4	Correct	135 ms	32000 KB	Output is correct
5	Correct	137 ms	32000 KB	Output is correct
6	Correct	134 ms	32032 KB	Output is correct
7	Correct	141 ms	32000 KB	Output is correct
8	Correct	140 ms	32024 KB	Output is correct
9	Correct	151 ms	32024 KB	Output is correct
10	Correct	174 ms	32120 KB	Output is correct
11	Correct	140 ms	32000 KB	Output is correct
12	Correct	142 ms	31992 KB	Output is correct
13	Correct	168 ms	32044 KB	Output is correct
14	Correct	150 ms	32052 KB	Output is correct
15	Correct	144 ms	32000 KB	Output is correct

Subtask #2

50.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	146 ms	32072 KB	Output is correct
2	Correct	140 ms	32000 KB	Output is correct
3	Correct	162 ms	32000 KB	Output is correct
4	Correct	154 ms	32000 KB	Output is correct
5	Correct	141 ms	32000 KB	Output is correct
6	Correct	138 ms	32000 KB	Output is correct
7	Correct	181 ms	32120 KB	Output is correct
8	Correct	174 ms	32120 KB	Output is correct
9	Correct	152 ms	32000 KB	Output is correct
10	Correct	152 ms	32120 KB	Output is correct
11	Correct	141 ms	32000 KB	Output is correct
12	Correct	199 ms	32076 KB	Output is correct
13	Correct	152 ms	32076 KB	Output is correct
14	Correct	154 ms	32120 KB	Output is correct
15	Correct	144 ms	32120 KB	Output is correct