제출 #772005

#제출 시각아이디문제언어결과실행 시간메모리
772005aaron_dcoder구경하기 (JOI13_watching)C++17
100 / 100
128 ms30164 KiB
//todo //ajihuwi #define NDEBUG #include <bits/stdc++.h> using namespace std; using ll = long long; //#define dbg(TXTMSG) cerr << "\n" << TXTMSG //#define dbgv(VARN) cerr << "\n" << #VARN << " = "<<VARN << ", line: " << __LINE__ << "\n" ll N, P/*small*/, Q/*big*/; vector<ll> A; vector<ll> covered_prefix_2w; vector<ll> covered_prefix_w; //constexpr ll MAX_N = 2002; //constexpr ll MAX_CAMERA = MAX_N; vector<vector<ll>> dp; bool is_cam_placement_possible(ll w) { ll w2_before_indice = 0; ll w_before_indice = 0; for (ll i = 0; i < N; i++) { while (A[w_before_indice] <= (A[i]-w)) { w_before_indice++; } while (A[w2_before_indice] <= (A[i]-2*w)) { w2_before_indice++; } covered_prefix_w[i]=w_before_indice; covered_prefix_2w[i]=w2_before_indice; } for (ll sectiontill = 1; sectiontill <= N; sectiontill++) { dp[sectiontill][0] = dp[covered_prefix_w[sectiontill-1]][0]+1; for (ll numbigcam = 1; numbigcam <= Q; numbigcam++) { dp[sectiontill][numbigcam] = min({ dp[covered_prefix_2w[sectiontill-1]][numbigcam-1], dp[covered_prefix_w[sectiontill-1]][numbigcam]+1 }); } if (dp[sectiontill][Q] > P) { return false; } if (dp[sectiontill][Q]+N-sectiontill <= P) { return true; } } return (dp[N][Q] <= P); } int main() { cin.tie(nullptr); cin.sync_with_stdio(false); cin >> N >> P >> Q; A = vector<ll>(N); covered_prefix_2w = vector<ll>(N); covered_prefix_w = vector<ll>(N); for (ll i = 0; i < N; i++) { cin >> A[i]; } sort(A.begin(),A.end()); if (N==0) { cout << "0"; return EXIT_SUCCESS; } if (N <= (P+Q)) { cout << "1"; return EXIT_SUCCESS; } dp.assign(N+1,vector<ll>(Q+1,0)); ll max_possible_w = 1ll + (*A.crbegin())/(P+Q); ll min_possible_w = 1ll; while (max_possible_w > min_possible_w) { ll mid = (max_possible_w+min_possible_w)/2; if (is_cam_placement_possible(mid)) { max_possible_w = mid; } else { min_possible_w = mid+1; } } cout << min_possible_w; } /* 13 3 2 33 66 99 10 83 68 19 83 93 53 15 66 75*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...