oj.uz

Submission #210613

# Submission time Handle Problem Language Result Execution time Memory
210613 2020-03-17T21:02:10 Z Blagojce Watching (JOI13_watching) C++11
100 / 100
 294 ms 31736 KB 
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
ll const inf = 1e9;
ll const mod = 1e9 + 7;
ld const eps = 1e-13;

ll n, p, q;
ll a[2000];

bool ok(ll w){
        ll dp[n + 1][q + 1];
        dp[0][0] = 0;
        fr(i, 1, q + 1) dp[0][i] = inf;

        fr(i, 1, n + 1){
                ll jlong = -1;
                ll jshort = -1;
                for(int j = i; j >= 1; j --){
                        if(a[i - 1] - a[j - 1] + 1 <= w) jshort = j;
                        if(a[i - 1] - a[j - 1] + 1 <= 2 * w) jlong = j;
                }
                fr(Q, 0, q + 1){
                        dp[i][Q] = inf;

                        if(Q > 0){
                                ll bef = 0;
                                bef = dp[jlong - 1][Q - 1];
                                dp[i][Q] = bef;
                        }
                        ll bef = 0;
                        bef = dp[jshort - 1][Q];
                        dp[i][Q] = min(dp[i][Q], bef + 1);
                }
        }
        ll BEST = inf;
        fr(i, 0, q + 1){
                BEST = min(BEST, dp[n][i]);
        }
        return BEST <= p;
}


void solve(){
        cin >> n >> p >> q;
        q = min(n, q);
        fr(i, 0, n){
                cin >> a[i];
        }
        sort(a, a + n);
        ll ans = 0;
        ll mx = 1e9;
        for(ll b = mx / 2; b >= 1; b /= 2){
                while(b + ans <= mx && !ok(b + ans)) ans += b;
        }
        cout << ans + 1<<endl;
}
int main()
{
        solve();
        return 0;
}

Subtask #1
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 236 ms 23804 KB Output is correct
4 Correct 83 ms 1528 KB Output is correct
5 Correct 288 ms 31608 KB Output is correct
6 Correct 287 ms 31736 KB Output is correct
7 Correct 113 ms 632 KB Output is correct
8 Correct 191 ms 12152 KB Output is correct
9 Correct 114 ms 2296 KB Output is correct
10 Correct 87 ms 1784 KB Output is correct
11 Correct 294 ms 30072 KB Output is correct
12 Correct 195 ms 15736 KB Output is correct
13 Correct 94 ms 632 KB Output is correct
14 Correct 103 ms 632 KB Output is correct
15 Correct 108 ms 632 KB Output is correct