oj.uz

Submission #642476

# Submission time Handle Problem Language Result Execution time Memory
642476 2022-09-19T14:26:13 Z BackNoob Watching (JOI13_watching) C++14
100 / 100
 236 ms 16212 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()
 
using namespace std;
const int mxN = 2007;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;
 
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
    if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
    if (a < b) {a = b; return true;} return false;
}
 
int n;
int p;
int q;
int a[mxN];
int nxt1[mxN];
int nxt2[mxN];
int dp[mxN][mxN];

bool ok(int x)
{
    int j1 = 1;
    int j2 = 1;
    for(int i = 1; i <= n; i++) {
        j1 = max(j1, i);
        j2 = max(j2, i);
        while(j1 < n && a[j1 + 1] - a[i] + 1 <= x) ++j1;
        while(j2 < n && a[j2 + 1] - a[i] + 1 <= 2 * x) ++j2;

        nxt1[i] = j1;
        nxt2[i] = j2;
    }


    memset(dp, 0x3f, sizeof(dp));
    int tmp = dp[0][0];
    dp[0][0] = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= p; j++) {
            if(dp[i][j] == tmp) continue;
            minimize(dp[nxt1[i + 1]][j + 1], dp[i][j]);
            minimize(dp[nxt2[i + 1]][j], dp[i][j] + 1);
        }
    }

    for(int j = 0; j <= p; j++) {
        if(dp[n][j] <= q) return true;
    }
    return false;
}
 
void solve()
{
    cin >> n >> p >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];

    p = min(p, n);
    q = min(q, n);

    sort(a + 1, a + 1 + n);
    int lo = 0, hi = inf;
    while(lo + 1 < hi) {
        int mid = (lo + hi) / 2;
        if(ok(mid)) hi = mid;
        else lo = mid;
    }

    cout << hi;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

 
    int tc = 1;
    //cin >> tc;
    while(tc--) {
        solve();
    }
    return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 16084 KB Output is correct
2 Correct 52 ms 16084 KB Output is correct
3 Correct 57 ms 16084 KB Output is correct
4 Correct 59 ms 16092 KB Output is correct
5 Correct 51 ms 16084 KB Output is correct
6 Correct 55 ms 16088 KB Output is correct
7 Correct 54 ms 16088 KB Output is correct
8 Correct 56 ms 16084 KB Output is correct
9 Correct 53 ms 16084 KB Output is correct
10 Correct 53 ms 16108 KB Output is correct
11 Correct 55 ms 16084 KB Output is correct
12 Correct 53 ms 16088 KB Output is correct
13 Correct 56 ms 16080 KB Output is correct
14 Correct 51 ms 16084 KB Output is correct
15 Correct 54 ms 16096 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 16084 KB Output is correct
2 Correct 53 ms 16084 KB Output is correct
3 Correct 199 ms 16112 KB Output is correct
4 Correct 228 ms 16116 KB Output is correct
5 Correct 69 ms 16084 KB Output is correct
6 Correct 226 ms 16112 KB Output is correct
7 Correct 60 ms 16112 KB Output is correct
8 Correct 75 ms 16116 KB Output is correct
9 Correct 135 ms 16112 KB Output is correct
10 Correct 236 ms 16116 KB Output is correct
11 Correct 73 ms 16112 KB Output is correct
12 Correct 194 ms 16212 KB Output is correct
13 Correct 57 ms 16112 KB Output is correct
14 Correct 58 ms 16112 KB Output is correct
15 Correct 57 ms 16112 KB Output is correct