Submission #1204942

#TimeUsernameProblemLanguageResultExecution timeMemory
1204942dio_2Radio Towers (IOI22_towers)C++20
15 / 100
257 ms1832 KiB
#include<bits/stdc++.h> using namespace std; // Observation 1: For every 2 towers we pick (i, j) |i - j| > 1 -> this means they cannot be adjacent. // Observation 2: Can(a, b) ^ Can(b, c) => Can(a, c) (so you only care if adjacent pairs can) int subtask1 = 0; int subtask2 = 0; int n; int point_k; int h[1000000]; int que = 0; void is1(int N, std::vector<int> H){ std::vector<int> isDec(N); // it should be decreasing to the right // so it should be increasing if we look at it from right. isDec[N - 1] = 1; for(int i = N - 2;i >= 0;i--){ isDec[i] = (isDec[i + 1] & (H[i] > H[i + 1])); } int inc = 1; point_k = 0; for(int i = 0;i < N;i++){ if(H[i] == H[i - 1]) break; if(i > 0) inc &= (H[i] > H[i - 1]); if(isDec[i] && inc){ subtask1 = 1; point_k = i; } } } int do1(int L, int R, int D){ if(!(L <= point_k && point_k <= R)) return 1; if(L == point_k || R == point_k) return 1; return (h[L] <= h[point_k] - D && h[R] <= h[point_k] - D) ? 2 : 1; } void is2(int N){ subtask2 |= (N <= 2000); } int do2(int L, int R, int D){ int ans = 1; std::vector<int> dp(n); dp[L] = 1; for(int i = L + 1;i <= R;i++){ dp[i] = 1; int mx = h[i - 1] - D; for(int j = i - 2;j >= 0;j--){ if(h[i] <= mx && h[j] <= mx) dp[i] = max(dp[i], dp[j] + 1); mx = max(mx, h[j] - D); } ans = max(ans, dp[i]); } return ans; } void init(int N, std::vector<int> H){ is1(N, H); is2(N); n = N; for(int i = 0;i < n;i++){ h[i] = H[i]; } } int max_towers(int L, int R, int D){ if(subtask1){ // we have a mountain. return do1(L, R, D); } que++; if(que == 1 && subtask2){ return do2(L, R, D); } assert(false); return 1; }
#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...