oj.uz

Submission #218799

# Submission time Handle Problem Language Result Execution time Memory
218799 2020-04-02T18:25:08 Z Haunted_Cpp Watching (JOI13_watching) C++17
100 / 100
 574 ms 16248 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 Get_Small (int p, int range) {
  if (~seguinte_small[p]) return seguinte_small[p];
  return seguinte_small[p] = (lower_bound(all(zona), zona[p] + range) - zona.begin());
}

int Get_Big (int p, int range) {
  if (~seguinte_big[p]) return seguinte_big[p];
  return seguinte_big[p] = (lower_bound(all(zona), zona[p] + 2 * range) - zona.begin());
}
 
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 (Get_Small(p, range), small - 1, range));
  }
  res = min (res, solve (Get_Big(p, range), 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));
    memset (seguinte_small, -1, sizeof(seguinte_small));
    memset (seguinte_big, -1, sizeof(seguinte_big));
    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 67 ms 16128 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 68 ms 16128 KB Output is correct
8 Correct 67 ms 16128 KB Output is correct
9 Correct 69 ms 16128 KB Output is correct
10 Correct 68 ms 16128 KB Output is correct
11 Correct 69 ms 16128 KB Output is correct
12 Correct 71 ms 16128 KB Output is correct
13 Correct 65 ms 16128 KB Output is correct
14 Correct 68 ms 16128 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 68 ms 16128 KB Output is correct
2 Correct 5 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 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 70 ms 16128 KB Output is correct
8 Correct 125 ms 16248 KB Output is correct
9 Correct 254 ms 16128 KB Output is correct
10 Correct 574 ms 16248 KB Output is correct
11 Correct 132 ms 16248 KB Output is correct
12 Correct 460 ms 16168 KB Output is correct
13 Correct 73 ms 16128 KB Output is correct
14 Correct 70 ms 16128 KB Output is correct
15 Correct 71 ms 16128 KB Output is correct