Submission #1204942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204942		dio_2	Radio Towers (IOI22_towers)	C++20	15 / 100	257 ms	1832 KiB

towers

#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;
}

• Subtask 1: 4 / 4
• Subtask 2: 11 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23