Submission #652140

#	Time	Username	Problem	Language	Result	Execution time	Memory
652140		pauloamed	Watching (JOI13_watching)	C++14	100 / 100	422 ms	16088 KiB

watching

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 2010;


int dp[MAXN][MAXN];
int v[MAXN];
int N, P, Q;

int go[MAXN][2];

bool can(int w){
  int last_0 = 0;
  int last_1 = 0;
  for(int i = 0; i < N; ++i){
    while(last_0 < N && v[last_0] - v[i] <= w - 1)
      last_0++;

    while(last_1 < N && v[last_1] - v[i] <= 2LL*w - 1)
      last_1++;

    go[i][0] = last_0;
    go[i][1] = last_1;

    // cout << i << " " << last_0 << " " << last_1 << "\n";
  }

  int maxp = min(N, P);
  for(int i = 0; i <= N; ++i){
    for(int j = 0; j <= maxp; ++j){
      dp[i][j] = INT_MAX;
    }
  }

  // P: w 0
  // Q: 2w 1
  dp[0][0] = 0;
  for(int i = 0; i < N; ++i){
    for(int j = 0; j <= maxp; ++j){
      if(dp[i][j] == INT_MAX) continue;
      dp[go[i][0]][j + 1] = min(dp[go[i][0]][j + 1], dp[i][j]);
      dp[go[i][1]][j] = min(dp[go[i][1]][j], dp[i][j] + 1);
    }
  }

  // cout << w << ":\n";
  int mini = INT_MAX;
  for(int j = 0; j <= maxp; ++j){
    // cout << j << " : " << dp[N][j] << "\n";
    mini = min(mini, dp[N][j]);
  }
  return mini <= Q;
}

int main(){
  cin.tie(NULL)->sync_with_stdio(false);
  cin >> N >> P >> Q;
  for(int i = 0; i < N; ++i) cin >> v[i];
  sort(v, v + N);

  // can(3);
  // return 0;

  int pot = (1 << 30);
  int ans = 0;
  while(pot){
    int mans = ans + pot;
    if(!can(mans)) ans = mans;
    pot /= 2;
  }
  cout << ans + 1 << "\n";
}

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