oj.uz

Submission #252218

# Submission time Handle Problem Language Result Execution time Memory
252218 2020-07-24T21:08:31 Z IgorI Watching (JOI13_watching) C++17
100 / 100
 254 ms 4376 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;

#define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define fi first
#define se second
#define re return
#define pb push_back
#define uniq(x) sort(all(x)); (x).resize(unique(all(x)) - (x).begin())

#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
#define ln cerr << __LINE__ << endl
#else
#define dbg(x) void(0)
#define ln void(0)
#endif // LOCAL

int cx[4] = {-1, 0, 1, 0};
int cy[4] = {0, -1, 0, 1};
string Yes[2] = {"No", "Yes"};
string YES[2] = {"NO", "YES"};

const int N = 3400;

int n, p, q;
int a[N];
int small[N], big[N];

int can(int M)
{
    int j = 0;
    for (int i = 0; i < n; i++)
    {
        while (j < n && a[j] - a[i] + 1 <= M) j++;
        small[i] = j;
    }
    small[n] = n;
    j = 0;
    for (int i = 0; i < n; i++)
    {
        while (j < n && a[j] - a[i] + 1 <= 2 * M) j++;
        big[i] = j;
    }
    big[n] = n;
    vector<vector<int> > dp(p + 1, vector<int>(q + 1));
    for (int s = 0; s <= p; s++)
    {
        for (int b = 0; b <= q; b++)
        {
            if (s < p)
            {
                dp[s + 1][b] = max(dp[s + 1][b], small[dp[s][b]]);
            }
            if (b < q)
            {
                dp[s][b + 1] = max(dp[s][b + 1], big[dp[s][b]]);
            }
        }
    }
    return (dp[p][q] == n);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> p >> q;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    if (p + q >= n)
    {
        cout << 1;
        return 0;
    }
    sort(a, a + n);
    int L = 0, R = 1e9 + 7;
    while (L + 1 < R)
    {
        int M = (L + R) / 2;
        if (can(M)) R = M;
        else L = M;
    }
    cout << R << "\n";
}

Subtask #1
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 26 ms 880 KB Output is correct
9 Correct 26 ms 836 KB Output is correct
10 Correct 47 ms 1228 KB Output is correct
11 Correct 45 ms 1184 KB Output is correct
12 Correct 254 ms 4376 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct