Submission #1106466

#TimeUsernameProblemLanguageResultExecution timeMemory
1106466xnqsWatching (JOI13_watching)C++17
0 / 100
1062 ms31824 KiB
#include <iostream> #include <fstream> #include <vector> #include <queue> #include <utility> #include <algorithm> #include <cstring> int x, p, q; std::vector<int> arr; std::vector<int> next[2]; std::pair<int,int> dp[2001][2001]; std::pair<int,int> solve(int pos, int k, int lambda) { if (pos==x) { return {0, 0}; } if (dp[pos][k].first!=-1) { return dp[pos][k]; } std::pair<int,int> ret(-0x3f3f3f3f, -0x3f3f3f3f); if (k<p) { ret = std::max(ret, std::pair<int,int>(solve(next[0][pos], k+1, lambda).first + next[0][pos]-pos, solve(next[0][pos], k+1, lambda).second)); } ret = std::max(ret, std::pair<int,int>(solve(next[1][pos], k, lambda).first + next[1][pos]-pos - lambda, solve(next[1][pos], k, lambda).second + 1)); return dp[pos][k] = ret; } bool can_solve(int cap) { if (double(p+q)/x >= 0.95 && cap >= 15) { return 1; } for (int i = 0; i < 2; i++) { next[i].resize(x); for (int l = x-1, r = x-1; l >= 0; l--) { while (arr[r]-arr[l]+1>(i+1)*cap) { --r; } next[i][l] = r+1; } } const auto bs_lambda = [&]() { int ret = -1; int l = 0, r = 2000; while (l<=r) { int m = (l+r)>>1; memset(dp,-1,sizeof(dp)); auto [max, cnt] = solve(0,0,m); if (cnt<=q) { ret = m; l = m+1; } else { r = m-1; } } return ret; }; int lambda = bs_lambda(); auto [max, cnt] = solve(0,0,lambda); return (max + cnt*lambda == x); } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL); std::cin >> x >> p >> q; // we only need at most x cameras in total, out of which we'll greedily take as many big cameras as possible if (p+q>x) { q = std::min(q, x); p = x-q; } for (int i = 0, tmp; i < x; i++) { std::cin >> tmp; arr.emplace_back(tmp); } std::sort(arr.begin(),arr.end()); const auto bs = [&]() { int ret = 1000000001; int l = 1, r = 1000000000; while (l<=r) { int m = (l+r)>>1; if (can_solve(m)) { ret = m; r = m-1; } else { l = m+1; } } return ret; }; std::cout << bs() << "\n"; //can_solve(bs(),1); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...