제출 #895526

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

watching

#include <bits/stdc++.h>
// define ctdl
#define ii pair<int,int>
#define fi first
#define se second
#define ll long long
// define files
#define TASKS "EVENTS."
#define fast ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
#define endl '\n'
#define all(x) x.begin(),x.end()

#define FORU(i,a,b) for(int i = a, _b = b; i <= _b ; i++)
#define FORD(i,a,b) for(int i = a, _b = b; i >= _b ; i--)


using namespace std;
const int maxsub1 = 200, maxn = 2000,oo = 1e9 ;
int n, numP, numQ ;
int a[maxn+1] ;

void getMin(int &x, int y)
{
    x = min(x,y) ;
}

namespace sub1
{
    int dp[maxn+1][maxn+1];
    bool check(int num)
    {
        memset(dp,0x3f,sizeof(dp)) ;
        dp[0][0] = 0 ;
        FORU(i,0,n) FORU(j,0,numP) if(dp[i][j] <= numQ)
        {
            int L = i + 1, R = i + 1 ;
            while(R <= n && a[L] + num-1 >= a[R] && j < numP)
            {
                getMin(dp[R][j+1],dp[i][j]) ;
                R++ ;
            }
            R = i + 1 ;
            while(R <= n && a[L] + num*2-1 >= a[R])
            {
                getMin(dp[R][j],dp[i][j] + 1) ;
                R++ ;
            }
        }
        FORU(j,0,numP) if(dp[n][j] <= numQ)
        {
            return true ;
        }
        return false ;
    }
    void solve()
    {
        int L = 1, R = 1e9,ans =0 ;
        while(L <= R)
        {
            int mid = (L+R)>>1 ;
            if(check(mid)) R = mid - 1,ans=mid;
            else L = mid + 1 ;
        }
        cout << ans ;
    }
}

namespace lastsub
{
    int dp[maxn+1][maxn+1] ;
    int p[maxn+1], q[maxn+1] ;
    bool check(int num)
    {
        memset(dp,0x3f,sizeof(dp)) ;
        dp[0][0] = 0 ;
        int tmp = 1 ;
        FORU(i,1,n)
        {
            while(tmp < n && a[i] + num - 1 >= a[tmp+1]) tmp++ ;
            p[i] = tmp ;
        }
        tmp = 1 ;
        FORU(i,1,n)
        {
            while(tmp < n && a[i] + num*2 - 1 >= a[tmp+1]) tmp++ ;
            q[i] = tmp ;
        }
        FORU(i,0,n) FORU(j,0,n) if(dp[i][j] <= numQ)
        {
            int R = p[i+1] ;
            getMin(dp[R][j+1],dp[i][j]) ;
            R = q[i+1] ;
            getMin(dp[R][j],dp[i][j] + 1) ;
        }
        FORU(j,0,numP) if(dp[n][j] <= numQ) return true ;
        return false ;
    }
    void solve()
    {
        int L = 1, R = 1e9,ans =0 ;
        while(L <= R)
        {
            int mid = (L+R)>>1 ;
            if(check(mid)) R = mid - 1,ans=mid;
            else L = mid + 1 ;
        }
        cout << ans ;
    }
}

int main()
{
    fast ;
    //freopen(TASKS"INP","r",stdin) ;
    //freopen(TASKS"OUT","w",stdout) ;
    cin >> n >> numP >> numQ ;
    FORU(i,1,n) cin >> a[i] ;
    sort(&a[1],&a[n+1]) ;
    if(n <= numP + numQ)
    {
        cout << 1 ;
        return 0 ;
    }
    if(n <= 100) sub1::solve() ;
    else lastsub::solve() ;
    return 0 ;
}

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