Submission #210602

# Submission time Handle Problem Language Result Execution time Memory
210602 2020-03-17T20:21:50 Z Blagojce Watching (JOI13_watching) C++11
0 / 100
74 ms 376 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;

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

bool ok(int w){
        int dp[n + 1][q + 1];
        dp[0][0] = 0;
        fr(i, 1, n + 1){
                int jlong;
                int jshort;
                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){
                                int bef = 0;
                                if(jlong > 0) bef = dp[jlong - 1][Q - 1];
                                dp[i][Q] = bef;
                        }
                        int bef = 0;
                        if(jshort > 0) bef = dp[jshort - 1][Q];
                        dp[i][Q] = min(dp[i][Q], bef + 1);
                }
        }
        int 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);
        sort(a, a + n);
        fr(i, 0, n){
                cin >> a[i];
        }
        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;
}

Compilation message

watching.cpp: In function 'bool ok(int)':
watching.cpp:24:21: warning: 'jlong' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 int jlong;
                     ^~~~~
watching.cpp:25:21: warning: 'jshort' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 int jshort;
                     ^~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -