oj.uz

Submission #170009

# Submission time Handle Problem Language Result Execution time Memory
170009 2019-12-23T15:33:56 Z WLZ Watching (JOI13_watching) C++14
100 / 100
 653 ms 16308 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int INF = 0x3f3f3f3f;

int n, p, q;
vector<int> a;

int check(int w) {
  vector< vector<int> > dp(n + 1, vector<int>(min(n, p) + 1, INF));
  dp[0][0] = 0;
  int x = 0, y = 0;
  for (int i = 0; i < n; i++) {
    while (x < n && a[x] - a[i] + 1 <= w) {
      x++;
    }
    while (y < n && a[y] - a[i] + 1 <= 2 * w) {
      y++;
    }
    for (int j = 0; j < min(n, p); j++) {
      dp[x][j + 1] = min(dp[x][j + 1], dp[i][j]);
      dp[y][j] = min(dp[y][j], dp[i][j] + 1);
    }
    dp[y][min(n, p)] = min(dp[y][min(n, p)], dp[i][min(n, p)] + 1);
  }
  for (int i = 0; i <= min(n, p); i++) {
    if (dp[n][i] <= q) {
      return 1;
    }
  }
  return 0;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> p >> q;
  a.resize(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  sort(a.begin(), a.end());
  int lo = 1, hi = (int) 1e9, ans;
  while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (check(mid)) {
      ans = mid;
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }
  cout << ans << '\n';
  return 0;
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:55:18: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   cout << ans << '\n';
                  ^~~~

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 3 ms 376 KB Output is correct
5 Correct 2 ms 248 KB Output is correct
6 Correct 3 ms 376 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 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 500 ms 12364 KB Output is correct
4 Correct 638 ms 16308 KB Output is correct
5 Correct 27 ms 1084 KB Output is correct
6 Correct 653 ms 16284 KB Output is correct
7 Correct 9 ms 632 KB Output is correct
8 Correct 42 ms 1516 KB Output is correct
9 Correct 235 ms 6512 KB Output is correct
10 Correct 641 ms 15516 KB Output is correct
11 Correct 31 ms 1144 KB Output is correct
12 Correct 314 ms 8320 KB Output is correct
13 Correct 8 ms 504 KB Output is correct
14 Correct 9 ms 632 KB Output is correct
15 Correct 9 ms 632 KB Output is correct