oj.uz

Submission #147279

# Submission time Handle Problem Language Result Execution time Memory
147279 2019-08-28T17:35:11 Z karma Watching (JOI13_watching) C++11
50 / 100
 615 ms 30288 KB 
#include<bits/stdc++.h>
#pragma GCC optimization ("O3")
#define ll  long long

using namespace std;

const int N = 2007;

ll n, pos[N], p, q, f[N][N];

bool Check(ll w)
{
     int k = 1, l;
     f[0][0] = 0;
     for(int j = 1; j <= n; ++j) {
        while(pos[j] - pos[k] >= 2 * w) ++k;
        f[0][j] = f[0][k - 1] + 1;
     }
     for(int i = 1; i <= p; ++i) {
        k = l = 1; f[i][0] = 0;
        for(int j = 1; j <= n; ++j) {
           while(pos[j] - pos[k] >= 2 * w) ++k;
           while(pos[j] - pos[l] >= w) ++l;
           f[i][j] = min({f[i][k - 1] + 1, f[i - 1][j], f[i - 1][l - 1]});
        }
     }
     return f[p][n] <= q;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    if(fopen("test.inp", "r")) {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    cin >> n >> p >> q;
    for(int i = 1; i <= n; ++i) cin >> pos[i];
    if(p + q >= n) return cout << 1, 0;
    sort(pos + 1, pos + n + 1);
    ll l = 0, h = (ll)1e9;
    while(l <= h) {
       ll mid = (l + h) >> 1;
       if(Check(mid)) h = mid - 1;
       else l = mid + 1;
    }
    cout << l;
}

Compilation message

watching.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
watching.cpp: In function 'int main()':
watching.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("test.inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("test.out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

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

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 8 ms 632 KB Output is correct
8 Correct 46 ms 2380 KB Output is correct
9 Correct 259 ms 12380 KB Output is correct
10 Incorrect 615 ms 30288 KB Output isn't correct
11 Halted 0 ms 0 KB -