oj.uz

Submission #895526

# Submission time Handle Problem Language Result Execution time Memory
895526 2023-12-30T07:34:51 Z nbphong Watching (JOI13_watching) C++14
100 / 100
 163 ms 17280 KB 
#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.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 17240 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 23 ms 17244 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 20 ms 17128 KB Output is correct
8 Correct 22 ms 17276 KB Output is correct
9 Correct 22 ms 17244 KB Output is correct
10 Correct 22 ms 17280 KB Output is correct
11 Correct 22 ms 17280 KB Output is correct
12 Correct 21 ms 17244 KB Output is correct
13 Correct 21 ms 17244 KB Output is correct
14 Correct 29 ms 17100 KB Output is correct
15 Correct 23 ms 17244 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 16988 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 100 ms 16988 KB Output is correct
8 Correct 116 ms 16988 KB Output is correct
9 Correct 108 ms 17036 KB Output is correct
10 Correct 106 ms 16984 KB Output is correct
11 Correct 144 ms 16984 KB Output is correct
12 Correct 163 ms 17036 KB Output is correct
13 Correct 100 ms 16988 KB Output is correct
14 Correct 100 ms 17056 KB Output is correct
15 Correct 116 ms 17056 KB Output is correct