oj.uz

Submission #306138

# Submission time Handle Problem Language Result Execution time Memory
306138 2020-09-24T16:05:03 Z quocnguyen1012 Watching (JOI13_watching) C++14
100 / 100
 222 ms 16120 KB 
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 2005;

int f[maxn][maxn];
int a[maxn], N;
int P, Q;

bool check(int len)
{
  const int inf = 1e9;
  int l = 1, r = 1;
  for (int i = 1; i <= N; ++i){
    while (l <= N && a[l] < a[i] - len + 1) ++l;
    while (r <= N && a[r] < a[i] - 2 * len + 1) ++r;
    for (int j = 0; j <= P; ++j){
      f[i][j] = inf;
      if (j > 0) f[i][j] = min(f[i][j], f[l - 1][j - 1]);
      f[i][j] = min(f[i][j], f[r - 1][j] + 1);
    }
  }
  return f[N][P] <= Q;
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  cin >> N >> P >> Q;
  for (int i = 1; i <= N; ++i){
    cin >> a[i];
  }
  sort(a + 1, a + 1 + N);
  if (P + Q >= N) {
    cout << 1;
    return 0;
  }
  int l = 1, r = 1e9, mid;
  while (l <= r){
    mid = (l + r) / 2;
    if (!check(mid)) l = mid + 1;
    else r = mid - 1;
  }
  cout << l;
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   37 |     freopen("A.INP", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
watching.cpp:38:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   38 |     freopen("A.OUT", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8352 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 9 ms 8448 KB Output is correct
8 Correct 21 ms 9216 KB Output is correct
9 Correct 103 ms 14208 KB Output is correct
10 Correct 222 ms 16000 KB Output is correct
11 Correct 17 ms 9088 KB Output is correct
12 Correct 130 ms 16120 KB Output is correct
13 Correct 8 ms 8448 KB Output is correct
14 Correct 8 ms 8448 KB Output is correct
15 Correct 9 ms 8448 KB Output is correct