oj.uz

Submission #218794

# Submission time Handle Problem Language Result Execution time Memory
218794 2020-04-02T18:21:21 Z Haunted_Cpp Watching (JOI13_watching) C++17
100 / 100
 541 ms 16376 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};

int dp [2005][2005];
int n;

vi zona;

int seguinte_small [2005];
int seguinte_big [2005];
 
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 (seguinte_small[p], small - 1, range));
  }
  res = min (res, solve (seguinte_big[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;
  }
  zona.resize(n);
  F0R (i, n) cin >> zona[i];
  sort (all(zona));
  int lo = 1, hi = 1e9 + 5;
  while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    memset (dp, -1, sizeof(dp));
    
    F0R (i, n) {
      seguinte_small[i] = (lower_bound(all(zona), zona[i] + mid) - zona.begin());
      seguinte_big[i] = (lower_bound(all(zona), zona[i] + 2 * mid) - zona.begin());
    }
    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 16128 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 68 ms 16128 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 256 KB Output is correct
7 Correct 69 ms 16124 KB Output is correct
8 Correct 71 ms 16128 KB Output is correct
9 Correct 68 ms 16128 KB Output is correct
10 Correct 68 ms 16128 KB Output is correct
11 Correct 70 ms 16120 KB Output is correct
12 Correct 68 ms 16128 KB Output is correct
13 Correct 66 ms 16120 KB Output is correct
14 Correct 68 ms 15992 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 16156 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 71 ms 16248 KB Output is correct
8 Correct 120 ms 16128 KB Output is correct
9 Correct 238 ms 16200 KB Output is correct
10 Correct 541 ms 16376 KB Output is correct
11 Correct 135 ms 16248 KB Output is correct
12 Correct 465 ms 16192 KB Output is correct
13 Correct 76 ms 16128 KB Output is correct
14 Correct 76 ms 16128 KB Output is correct
15 Correct 76 ms 16128 KB Output is correct