제출 #895528

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
895528		nbphong	구경하기 (JOI13_watching)	C++14	100 / 100	146 ms	17752 KiB

watching

#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ff first
#define ss second
#define For(i,a,b) for(int i = (a), _b= (b) ; i<=_b ; i++)
#define pii pair<int,int>
#define ll long long
#define all(a) a.begin(),a.end()
#define pll pair<ll,ll>
#define pb push_back
#define AF "EVENTS"
using namespace std ;
const int N = 2100;
const int MOD = 998244353;
int f[N][N],n,w1,w2,a[N];
bool minimize(int &a,int b)
{
    if(a>b){
        a=b;return true;
    }else return false;
}
bool check(int mid)
{
    int l1=1,l2=1;
    memset(f,0x3f,sizeof f);
    memset(f[0],0,sizeof f[0]);
    For(i,1,n)
    {
        while(a[i]-a[l1]+1>mid) l1++;
        while(a[i]-a[l2]+1>2*mid) l2++;
        For(j,0,w1)
        {
            minimize(f[i][j+1],f[l1-1][j]);
            minimize(f[i][j],f[l2-1][j]+1);
        }
    }
    For(j,0,w1)  if(f[n][j]<=w2) return true;
    return false;
}
void enter()
{
    cin >> n >> w1 >> w2;
    if(w1+w2>=n){cout << 1; return;}
    For(i,1,n) cin >> a[i];
    sort(&a[1],&a[n+1]);
    int l = 1,r = 1e9;
    while(l<=r)
    {
        int mid = (l+r)>>1;
        if(check(mid)) r = mid-1;
        else l = mid+1;
    }
    cout << r+1;
}
void solve()
{

}
int main()
{
    fast;
    //freopen(AF".inp","r",stdin);
   // freopen(AF".out","w",stdout);
    enter();
    solve();
}

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