Submission #1119012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119012		vjudge1	Watching (JOI13_watching)	C++17	100 / 100	133 ms	32012 KiB

watching

#include <bits/stdc++.h>
 
 
#define                int  long long
#define                pii  pair<int, int>
#define                 fi  first
#define                 se  second
#define                 ld  long double
#define                 vi  vector<int>
#define                vii  vector<vector<int>>
#define             all(v)  (v).begin(), (v).end()
#define       rep(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i)
#define       per(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i)
 
using namespace std;
 
const int MOD = 1e9 + 7;
 
int add(int a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
  return a;
}
 
int mul(int a, int b) {
  (a *= b) %= MOD;
  return a;
}
 
int ceil(int x, int y) {
  return (x + y - 1) / y;
}
 
int bin_pow(int x, int y) {
  int res=1;
  while(y){if(y&1)res=res*x%MOD;x=x*x%MOD;y>>=1;}
  return res;
}
 
const int INF = 1e17;
const int maxn = 1e6 + 5;
 
int n, p, q;
int a[maxn + 5];
int rw[maxn + 5], r2w[maxn + 5];
int dp[2005][2005];
 
bool check(int w) {
  for (int i = 1; i <= n; ++i) {
    for (int j = i; j <= n; ++j) {
      if (a[j] - a[i] + 1 <= w)
        rw[i] = j;
      if (a[j] - a[i] + 1 <= 2 * w)
        r2w[i] = j;
      else
        break;
    }
  }
  memset(dp, 0, sizeof dp);
  dp[1][0] = rw[1];
  dp[0][1] = r2w[1];
  for (int i = 0; i <= p; ++i) {
    for (int j = 0; j <= q; ++j) {
      if (dp[i][j] == n) return true;
      if (i < p)
        dp[i + 1][j] = max(dp[i + 1][j], rw[dp[i][j] + 1]);
      if (j < q)
        dp[i][j + 1] = max(dp[i][j + 1], r2w[dp[i][j] + 1]);
    }
  }
  return false;
}
 
void solve(int tc) {
  cin >> n >> p >> q;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  if (p + q >= n) {
    cout << 1;
    return;
  }
  sort(a + 1, a + n + 1);
  int l = 1, r = a[n], ans;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (check(mid)) {
      ans = mid;
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  cout << ans;
}
 
signed main() {
 
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
 
  int tc = 1;
  //cin >> tc;
 
  for (int i = 1; i <= tc; ++i) {
    solve(i);
  }
}

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