oj.uz

Submission #218756

# Submission time Handle Problem Language Result Execution time Memory
218756 2020-04-02T17:17:00 Z Haunted_Cpp Watching (JOI13_watching) C++17
50 / 100
 147 ms 262148 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 = 1e5 + 5;
int n;

vi zona;

vector< vector< vector<int> > > dp;

int solve (int p, int big, int small, int range) {
  if (p >= n) return 1;
  int &res = dp[p][big][small];
  if (~res) return res;
  res = 0;
  if (small) {
    int next_location = (lower_bound (all(zona), zona[p] + range) - zona.begin());
    res = max (res, solve (next_location, big, small - 1, range));
  }
  if (big) {
    int next_location = (lower_bound (all(zona), zona[p] + 2 * range) - zona.begin());
    res = max (res, solve (next_location, big - 1, small, range));
  }
  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;
    dp = vector< vector< vector<int> > > (n + 5, vector< vector<int> > (big + 5, vi (small + 5, -1)));
    if ( solve (0, big, small, mid) ) 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 6 ms 384 KB Output is correct
2 Correct 5 ms 304 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 6 ms 512 KB Output is correct
8 Correct 8 ms 640 KB Output is correct
9 Correct 8 ms 512 KB Output is correct
10 Correct 20 ms 1920 KB Output is correct
11 Correct 16 ms 1616 KB Output is correct
12 Correct 31 ms 3344 KB Output is correct
13 Correct 7 ms 512 KB Output is correct
14 Correct 6 ms 512 KB Output is correct
15 Correct 6 ms 512 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1792 KB Output is correct
2 Correct 5 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 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 77 ms 9472 KB Output is correct
8 Runtime error 147 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -