제출 #937506

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
937506		vjudge1	구경하기 (JOI13_watching)	C++17	0 / 100	3 ms	356 KiB

watching

#pragma GCC optimize("Ofast")
 
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define ld long double
#define pb push_back //emplace_back
#define pp pop_back
#define pii pair<ll, ll> //pair<int, int>
#define all(x) (x).begin(),(x).end()
#define mp(a,b) make_pair(a , b)
#define sz(x) (ll)(x).size()
#define F first
#define S second
#define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
#define debug(x) cout << #x << " : " << x << endl << flush
#define endl '\n'
#define arr(x) array<ll , (x)>
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);
 
ll Sum(ll a , ll b , ll MOD)
{
 a %= MOD;
 b %= MOD;
 a += b;
 return a % MOD;
}
 
ll Mul(ll a , ll b , ll MOD)
{
 a %= MOD;
 b %= MOD;
 a *= b;
 return a % MOD;
}
 
ll Pow(ll a , ll b , ll MOD)
{
   ll res = 1;
   while(b)
   {
        if((b & 1))res = Mul(res , a , MOD);
     a = Mul(a , a , MOD);
     b >>= 1;
   }
   return res;
}
 
ll Min(ll a , ll b)
{
   if(a > b)return b;
   return a;
}
 
ll Max(ll a , ll b)
{
   if(a > b)return a;
   return b;
}
 
ll Ceil(ll a , ll b)
{
 if(a % b)return (a/b)+1;
 return a/b;
}
 
/////////////////////
//VALS
ll n, p, q;
const ll maxn = 2e3+10;
const ll INF = 1e18;
ll a[maxn];
/////////////////////
//FUNCTIONS
bool chk(ll x)
{
//	debug(x);
	ll dp[n+1][p+1];//dp[i][j] -> until pref i, if we have j small , what is the minimum number of large we need
	ll lstsmall[n], lstbig[n];
	
	For(i, n)
		lstsmall[i] = lower_bound(a, a+n, a[i] - x + 1) - a;
	For(i, n)
		lstbig[i] = lower_bound(a, a+n, a[i] - x - x + 1) - a;
//	if(x == 5)
//	For(i, n)
//	{
//		debug(i);
//		debug(lstsmall[i]);
//		debug(lstbig[i]);
//	}
//	debug("_____________________");
 
	For(i, p+1)dp[0][i] = 0;
	
    for (int i = 1; i <= n; i++)
    {
        For(j, p+1)
        {
            dp[i][j] = 1e18;
            dp[i][j] = min(dp[i][j], dp[lstbig[i-1] - 1][j] + 1);
 
            if (j >= 1)
            {
                dp[i][j] = min(dp[i][j], dp[i][j - 1]);
                dp[i][j] = min(dp[i][j], dp[lstsmall[i-1] - 1][j - 1]);
            }
        }
    }
	
	For(i, p+1)
	{
//		debug(i);
//		debug(dp[n][i]);
		if(dp[n][i] <= q)return 1;	
	}
	return 0;
}
/////////////////////
//SOLVE
void solve()
{
	cin >> n >> p >> q;
	
	For(i, n)cin >> a[i];
	For(i, n)a[i]--;
	
	if(p + q >= n)
	{
		cout << 1 << endl;
		return;
	}
	
	ll l = 0, r = 1e9;
	
	while(r - l > 1)
	{
//		debug(":L");
		ll mid = (r + l) >> 1;
		if(chk(mid))r = mid;
		else l = mid;
	}
	
	cout << r << endl;
}
/////////////////////
//MAIN
int main()
{
    FAST;
    ll t = 1;
//    cin >> t;
    while(t--)
    {
        solve();
    }
}
/////////////////////
/*
ZZZZZZZ     A        M     M     IIIIIII  N     N
     Z     A A      M M   M M       I     NN    N
    Z     A   A    M   M M   M      I     N N   N
   Z     AAAAAAA  M     M     M     I     N  N  N
  Z      A     A  M           M     I     N   N N
 Z       A     A  M           M     I     N    NN
ZZZZZZZ  A     A  M           M  IIIIIII  N     N  TREE
*/

컴파일 시 표준 에러 (stderr) 메시지

watching.cpp: In function 'bool chk(long long int)':
watching.cpp:17:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
      |                           ^
watching.cpp:85:2: note: in expansion of macro 'For'
   85 |  For(i, n)
      |  ^~~
watching.cpp:17:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
      |                           ^
watching.cpp:87:2: note: in expansion of macro 'For'
   87 |  For(i, n)
      |  ^~~
watching.cpp:17:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
      |                           ^
watching.cpp:98:2: note: in expansion of macro 'For'
   98 |  For(i, p+1)dp[0][i] = 0;
      |  ^~~
watching.cpp:17:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   17 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
      |                           ^
watching.cpp:102:9: note: in expansion of macro 'For'
  102 |         For(j, p+1)
      |         ^~~
watching.cpp:17:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
      |                           ^
watching.cpp:115:2: note: in expansion of macro 'For'
  115 |  For(i, p+1)
      |  ^~~
watching.cpp: In function 'void solve()':
watching.cpp:17:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
      |                           ^
watching.cpp:129:2: note: in expansion of macro 'For'
  129 |  For(i, n)cin >> a[i];
      |  ^~~
watching.cpp:17:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
      |                           ^
watching.cpp:130:2: note: in expansion of macro 'For'
  130 |  For(i, n)a[i]--;
      |  ^~~

• Subtask 1: 0 / 50
• Subtask 2: 0 / 50