oj.uz

답안 #306337

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
306337 2020-09-25T09:10:27 Z syy 구경하기 (JOI13_watching) C++17
50 / 100
 1000 ms 32120 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define sandybridge __attribute__((optimize("Ofast"), target("arch=sandybridge")))

ll n, p, q, A[2005], w, upper, lower, dp[2005][2005];

ll f(ll index, ll bigCamsNeeded) { //Min p that can cover everything
  if (index < 0) return 0;
  if (dp[index][bigCamsNeeded] != -1) return dp[index][bigCamsNeeded]; //If calculated
  dp[index][bigCamsNeeded] = LLONG_MAX;
  if (bigCamsNeeded > 0) {
    ll ind = upper_bound(A, A + n, A[index] - w - w) - A - 1; //Cannot take
    dp[index][bigCamsNeeded] = f(ind, bigCamsNeeded - 1);
  }
  ll ind = upper_bound(A, A + n, A[index] - w) - A - 1;
  dp[index][bigCamsNeeded] = min(dp[index][bigCamsNeeded], f(ind, bigCamsNeeded) + 1); // You used one more small camera so need + 1
  return dp[index][bigCamsNeeded];
}

int main() {
    fastio;
  cin >> n >> p >> q;
  if (p + q >= n) {
    cout << 1;
    return 0;
  }
  for (ll i = 0; i < n; i++) cin >> A[i];
  sort(A, A + n);
  lower = 0; upper = A[n - 1] + 1;
  while (upper - lower > 1) {
  	memset(dp, -1, sizeof dp); //Not calculated before.
    w = lower + (upper - lower) / 2;
    if (f(n - 1, q) <= p) upper = w;
    else lower = w;
  }
  cout << upper;
}

Subtask #1
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 156 ms 31864 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 153 ms 31848 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 157 ms 31744 KB Output is correct
8 Correct 153 ms 31744 KB Output is correct
9 Correct 147 ms 31744 KB Output is correct
10 Correct 158 ms 31864 KB Output is correct
11 Correct 156 ms 31744 KB Output is correct
12 Correct 155 ms 31744 KB Output is correct
13 Correct 151 ms 31744 KB Output is correct
14 Correct 140 ms 31864 KB Output is correct
15 Correct 153 ms 31756 KB Output is correct

Subtask #2
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 159 ms 31872 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 159 ms 31872 KB Output is correct
8 Correct 914 ms 32120 KB Output is correct
9 Correct 403 ms 31992 KB Output is correct
10 Correct 473 ms 31992 KB Output is correct
11 Execution timed out 1092 ms 31992 KB Time limit exceeded
12 Halted 0 ms 0 KB -