oj.uz

Submission #218788

# Submission time Handle Problem Language Result Execution time Memory
218788 2020-04-02T18:15:41 Z Haunted_Cpp Watching (JOI13_watching) C++17
50 / 100
 1000 ms 16252 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 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) {
    int next_location = (lower_bound (all(zona), zona[p] + range) - zona.begin());
    res = min (res, solve (next_location, small - 1, range));
  }
  int next_location = (lower_bound (all(zona), zona[p] + 2 * range) - zona.begin());
  res = min (res, solve (next_location, 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));
    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 16120 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 68 ms 16120 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 69 ms 16128 KB Output is correct
8 Correct 72 ms 16128 KB Output is correct
9 Correct 69 ms 16128 KB Output is correct
10 Correct 70 ms 16128 KB Output is correct
11 Correct 72 ms 16128 KB Output is correct
12 Correct 74 ms 16112 KB Output is correct
13 Correct 67 ms 16000 KB Output is correct
14 Correct 68 ms 16120 KB Output is correct
15 Correct 68 ms 16000 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 16128 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 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 5 ms 384 KB Output is correct
7 Correct 72 ms 16128 KB Output is correct
8 Correct 327 ms 16128 KB Output is correct
9 Correct 935 ms 16252 KB Output is correct
10 Execution timed out 1096 ms 16128 KB Time limit exceeded
11 Halted 0 ms 0 KB -