Submission #1283174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283174		thuhienne	Watching (JOI13_watching)	C++20	0 / 100	6 ms	8256 KiB

watching

#include <bits/stdc++.h>
using namespace std;

#define re exit(0);
#define thuhien "JOI13_Watching"

int n,p,q,event[2009];

int dp[2009][1009];
//dp i j: khi xet den i va con lai j doan loai 1 thi so doan loai 2 con lai max nhat
//la bao nhieu

int _1[2009],_2[2009];

bool check(int w) {
	int pt = 1;
	for (int i = 1;i <= n;i++) {
		while (event[i] - event[pt] + 1 > w) pt++;
		_1[i] = pt;
	}
	pt = 1;
	for (int i = 1;i <= n;i++) {
		while (event[i] - event[pt] + 1 > 2*w) pt++;
		_2[i] = pt;
	}
	
	for (int i = 0;i <= n;i++) {
		for (int j = 0;j <= min(p,q) + 3;j++) dp[i][j] = -1e9;
	}
	
	if (p < q) {
		
		dp[0][p] = q;
		for (int i = 1;i <= n;i++) {
			for (int j = 0;j <= p;j++) {
				int pos;
				//dung loai to
				pos = _2[i] - 1;
				dp[i][j] = max(dp[i][j],dp[pos][j + 1]);
				//dung loai nho
				pos = _1[i] - 1;
				dp[i][j] = max(dp[i][j],dp[pos][j] - 1);
			}
		}
		for (int j = 0;j <= p;j++) if (dp[n][j] >= 0) return 1;
		return 0;
		
	} else {
		dp[0][q] = p;
		for (int i = 1;i <= n;i++) {
			for (int j = 0;j <= q;j++) {
				int pos;
				//dung loai to
				pos = _2[i] - 1;
				dp[i][j] = max(dp[i][j],dp[pos][j] - 1);
				//dung loai nho
				pos = _1[i] - 1;
				dp[i][j] = max(dp[i][j],dp[pos][j + 1]);
			}
		}
		for (int j = 0;j <= q;j++) if (dp[n][j] >= 0) {
			return 1;
		}
		return 0;
	}
}

int main() {
//  ios_base::sync_with_stdio(0);cin.tie(nullptr);
	if (fopen(thuhien".inp","r")) {
		freopen(thuhien".inp","r",stdin);
		freopen(thuhien".out","w",stdout);
	}
	
	cin >> n >> p >> q;
	for (int i = 1;i <= n;i++) cin >> event[i];
	sort(event + 1,event + 1 + n);
	
	for (int i = 1;i <= n;i++) cout << event[i] << " ";
	cout << '\n';
	if (p + q >= n) {
		cout << 1;
		return 0;
	}
	
	int l = 1,r = *max_element(event + 1,event + 1 + n) / 2;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (check(mid)) r = mid - 1;
		else l = mid + 1;
	}
	cout << l;

//	cout << check(8);
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:71:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |                 freopen(thuhien".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:72:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |                 freopen(thuhien".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 50
• Subtask 2: 0 / 50