Submission #1073473

#TimeUsernameProblemLanguageResultExecution timeMemory
1073473fv3Radio Towers (IOI22_towers)C++17
0 / 100
4086 ms2956 KiB
#include "towers.h" #include <bits/stdc++.h> using namespace std; const int INF = 1 << 30; int N; vector<int> H; void init(int N_, vector<int> H_) { N = N_; H = H_; } int max_towers(int L, int R, int D) { // You should always lease the smallest tower // No two adjacent towers can be leased int res = 0; vector<int> leased(N); vector<int> neighbour(N); while (true) { int mn = INF; int mn_index = -1; for (int i = L; i <= R; i++) { if (!leased[i] && !neighbour[i] && H[i] < mn) { mn = H[i]; mn_index = i; } } if (mn == INF) break; int mx = mn; for (int i = mn_index + 1; i <= R; i++) { if (leased[i]) { if (mx - mn < D) return res; } else { mx = max(mx, H[i]); } } mx = mn; for (int i = mn_index - 1; i >= L; i--) { if (leased[i]) { if (mx - mn < D) return res; } else { mx = max(mx, H[i]); } } res++; leased[mn_index] = 1; if (mn_index > L) neighbour[mn_index-1] = 1; if (mn_index < R) neighbour[mn_index+1] = 1; } return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...