oj.uz

Submission #575438

# Submission time Handle Problem Language Result Execution time Memory
575438 2022-06-10T12:47:22 Z Huy Watching (JOI13_watching) C++17
100 / 100
 66 ms 8644 KB 
#include<bits/stdc++.h>
//#define int long long
#define pii pair<ll,ll>
#define fi first
#define se second

using namespace std;
using ll = long long;
using ldb = long double;
const int N = (int)5e5+2;
const int maxN = (int)1e5 + 5;
const int mod = 1e9 + 7;
const ll infty = 1e10;

void InputFile()
{
    //freopen("scrivener.inp","r",stdin);
    //freopen("scrivener.out","w",stdout);
    //freopen("test.out","r",stdin);
}

void FastInput()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

int n,P,Q;
int a[2005];

void Read()
{
    cin >> n >> P >> Q;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    sort(a + 1,a + n + 1);
}

int r1[2005];
int r2[2005];
int dp[2005][2005];
bool Check(int d)
{
    for(int i = 1;i <= n;i++)
    {
        int su = a[i] + d - 1;
        r1[i] = upper_bound(a + i,a + n + 1,su) - a - 1;
        su = a[i] + 2 * d - 1;
        r2[i] = upper_bound(a + i,a + n + 1,su) - a - 1;
    }
    r1[n+1] = r2[n+1] = n;
    dp[0][0] = 0;
    for(int i = 1;i <= P;i++)
    {
        dp[i][0] = r1[dp[i-1][0]+1];
        if(dp[i][0] >= n) return true;
    }
    for(int j = 1;j <= Q;j++)
    {
        dp[0][j] = r2[dp[0][j-1]+1];
        if(dp[0][j] >= n) return true;
    }
    for(int i = 1;i <= P;i++)
    {
        for(int j = 1;j <= Q;j++)
        {
            dp[i][j] = max(r1[dp[i-1][j]+1],r2[dp[i][j-1]+1]);
            if(dp[i][j] >= n) return true;
        }
    }
    return false;
}

void Solve()
{
    if(P + Q >= n) {cout << 1;return;}
    int low = 1;
    int high = 1e9;
    while(low <= high)
    {
        int mid = (low + high) / 2;
        if(Check(mid)) high = mid - 1;
        else low = mid + 1;
    }
    cout << low;
}

void Debug()
{
    //Main_sub();
    //Naive();
}


int32_t main()
{
    FastInput();
    //InputFile();
    //int sub_type;
    //cin >> sub_type;
    //Sieve();
    int test;
    //cin >> test;
    test = 1;
    while(test--)
        //for(int prc = 1; prc <= test; prc++)
    {
        Read();
        Solve();
        //Debug();
    }
}

/*
13 1
769 514 336 173 181 373 519 338 985 709 729 702 168
12 581
*/

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 324 KB Output is correct
15 Correct 1 ms 340 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 5 ms 356 KB Output is correct
8 Correct 14 ms 1232 KB Output is correct
9 Correct 13 ms 3760 KB Output is correct
10 Correct 13 ms 8644 KB Output is correct
11 Correct 10 ms 980 KB Output is correct
12 Correct 66 ms 8020 KB Output is correct
13 Correct 3 ms 340 KB Output is correct
14 Correct 4 ms 340 KB Output is correct
15 Correct 3 ms 340 KB Output is correct