oj.uz

Submission #218805

# Submission time Handle Problem Language Result Execution time Memory
218805 2020-04-02T18:36:28 Z Haunted_Cpp Watching (JOI13_watching) C++17
100 / 100
 538 ms 16264 KB 
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <cassert>
#include <string>
#include <cstring>
#include <bitset>
#include <random>
#include <chrono>
 
#define FOR(i, a, b) for(int i = a; i < (int) b; i++)
#define F0R(i, a) FOR (i, 0, a)
#define ROF(i, a, b) for(int i = a; i >= (int) b; i--)
#define R0F(i, a) ROF(i, a, 0)
#define GO(i, a) for (auto i : a)
 
#define rsz resize
#define eb emplace_back
#define pb push_back
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define f first
#define s second
 
using namespace std;
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef vector<vpii> vvpii;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef vector<pi64> vpi64;
 
const int dr[] = {+1, -1, +0, +0, +1, -1, +1, -1};
const int dc[] = {+0, +0, +1, -1, +1, -1, -1, +1};
const int ms[] = {+31, +29, +31, 30, +31, +30, +31, +31, +30, +31, +30, +31};
 
const int N = 2e3 + 5;
int dp [N][N];
int n, nxt1 [N], nxt2 [N], zona [N];
 
int solve (int p, int small, int range) {
  if (p >= n) return 0;
  int &res = dp[p][small];
  if (~res) return res;
  res = 1e9;
  if (small) res = min (res, solve (nxt1[p], small - 1, range));
  res = min (res, solve (nxt2[p], small, range) + 1);
  return res;
}
 
int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int small, big;
  cin >> n >> small >> big;
  if (small + big >= n) {
    cout << 1 << '\n';
    return 0;
  }
  F0R (i, n) cin >> zona[i];
  sort (zona, zona + n);
  int lo = 1, hi = 1e9 + 5;
  while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    memset (dp, -1, sizeof(dp));  
    F0R (i, n) {
      nxt1[i] = (lower_bound (zona, zona + n, zona[i] + mid) - zona);
      nxt2[i] = (lower_bound (zona, zona + n, zona[i] + 2 * mid) - zona);
    }
    if ( solve (0, small, mid) <= big) hi = mid;
    else lo = mid + 1;
  }
  cout << hi << '\n';  
  return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 16120 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 69 ms 16128 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 72 ms 16248 KB Output is correct
8 Correct 69 ms 16124 KB Output is correct
9 Correct 77 ms 16120 KB Output is correct
10 Correct 75 ms 16120 KB Output is correct
11 Correct 69 ms 16128 KB Output is correct
12 Correct 71 ms 16128 KB Output is correct
13 Correct 68 ms 16256 KB Output is correct
14 Correct 69 ms 16120 KB Output is correct
15 Correct 68 ms 16128 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 16128 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 73 ms 16128 KB Output is correct
8 Correct 122 ms 16128 KB Output is correct
9 Correct 233 ms 16128 KB Output is correct
10 Correct 538 ms 16264 KB Output is correct
11 Correct 134 ms 16128 KB Output is correct
12 Correct 456 ms 16248 KB Output is correct
13 Correct 75 ms 16128 KB Output is correct
14 Correct 75 ms 16128 KB Output is correct
15 Correct 75 ms 16128 KB Output is correct