Submission #306337

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
306337	2020-09-25T09:10:27 Z	syy	Watching (JOI13_watching)	C++17	50 / 100	1000 ms	32120 KB

watching

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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	-