Submission #230722

#	Time	Username	Problem	Language	Result	Execution time	Memory
230722		AlexLuchianov	Watching (JOI13_watching)	C++14	100 / 100	336 ms	16184 KiB

watching

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 2000;
int const inf = 1000000000;
int v[1 + nmax];
int n, p, q;
int dp[1 + nmax][1 + nmax];

int test(int target){
  for(int i = 0; i <= n; i++)
    for(int j = 0; j <= p; j++)
      dp[i][j] = n + 1;
  dp[0][0] = 0;
  for(int i = 1;i <= n; i++) {
    int p1 = i, p2 = i;
    while(1 <= p1 && v[i] - v[p1] + 1 <= target)
      p1--;
    while(1 <= p2 && v[i] - v[p2] + 1 <= 2 * target)
      p2--;

    for(int j = 1; j <= p; j++)
      dp[i][j] = min(dp[i][j], dp[p1][j - 1]);
    for(int j = 0; j <= p; j++)
      dp[i][j] = min(dp[i][j], dp[p2][j] + 1);
  }
  for(int i = 0;i <= p; i++)
    if(dp[n][i] <= q)
      return 1;
  return 0;
}

int binarysearch(int from, int to){
  if(from < to){
    int mid = (from + to) / 2;
    if(test(mid) == 1)
      return binarysearch(from, mid);
    else
      return binarysearch(mid + 1, to);
  } else
    return from;
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> p >> q;
  p = min(n, p);
  q = min(n, q);
  for(int i = 1; i <= n; i++)
    cin >> v[i];
  sort(v + 1, v + n + 1);
  cout << binarysearch(1, inf);

  return 0;
}

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50