oj.uz

Submission #106860

# Submission time Handle Problem Language Result Execution time Memory
106860 2019-04-20T18:54:01 Z someone_aa Watching (JOI13_watching) C++17
100 / 100
 672 ms 17016 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 2100;
int n, p, q;
set<int>st;
vector<int>v;
int dp[maxn][maxn];

bool check(ll x) {
    for(int i=0;i<=v.size();i++) {
        for(int j=0;j<=v.size();j++) {
            dp[i][j] = 10000000;
        }
    }
    dp[0][0] = 0;

    int result = INT_MAX;

    int lst = 1, lst2=1;
    for(int i=1;i<=v.size();i++) {
        //cout<<i<<":\n";

        while(v[i-1] - v[lst-1] >= x && lst < i) lst++;
        while(v[i-1] - v[lst2-1] >= 2*x && lst2 < i) lst2++;

        for(int j=0;j<=q;j++) {

            if(v[i-1] - v[lst-1] < x) {
                dp[i][j] = min(dp[i][j], dp[lst-1][j]+1);
                if(j-1>=0) {
                    dp[i][j] = min(dp[i][j], dp[lst-1][j-1]);
                }
            }

            if(v[i-1] - v[lst2-1] < 2*x && j>=1) {
                dp[i][j] = min(dp[i][j], dp[lst2-1][j-1]);
            }

            //cout<<j<<": "<<dp[i][j]<<"\n";
            if(i == v.size()) {
                result = min(result, dp[i][j]);
            }
        }
    }
    return result <= p;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>p>>q;

    int x;
    for(int i=1;i<=n;i++) {
        cin>>x;
        st.insert(x);
    }

    for(int i:st) {
        v.pb(i);
    }
    q = min(q, int(v.size()));


    ll l = 0LL, r = 1LL * 1e9;
    ll result = LLONG_MAX;
    while(l < r) {
        ll mid = (l + r) / 2;

        if(check(mid)) {
            result = min(result, mid);
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }
    cout<<result<<"\n";
    return 0;
}

Compilation message

watching.cpp: In function 'bool check(long long int)':
watching.cpp:13:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<=v.size();i++) {
                 ~^~~~~~~~~~
watching.cpp:14:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<=v.size();j++) {
                     ~^~~~~~~~~~
watching.cpp:23:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<=v.size();i++) {
                 ~^~~~~~~~~~
watching.cpp:43:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(i == v.size()) {
                ~~^~~~~~~~~~~

Subtask #1
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 17016 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 452 ms 16888 KB Output is correct
4 Correct 126 ms 16768 KB Output is correct
5 Correct 672 ms 16904 KB Output is correct
6 Correct 572 ms 17012 KB Output is correct
7 Correct 107 ms 16888 KB Output is correct
8 Correct 272 ms 16832 KB Output is correct
9 Correct 140 ms 16888 KB Output is correct
10 Correct 122 ms 16896 KB Output is correct
11 Correct 543 ms 16944 KB Output is correct
12 Correct 402 ms 16976 KB Output is correct
13 Correct 111 ms 16896 KB Output is correct
14 Correct 101 ms 16948 KB Output is correct
15 Correct 110 ms 16944 KB Output is correct