QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#546301#8776. Not Another Constructive!Djangle162857WA 0ms3560kbC++202.2kb2024-09-03 22:36:532024-09-03 22:36:54

Judging History

你现在查看的是最新测评结果

  • [2024-09-03 22:36:54]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3560kb
  • [2024-09-03 22:36:53]
  • 提交

answer

#include <bits/stdc++.h>
#define fir first
#define sec second
#define FINISH cout << "FINISH" << endl;
#define debug(x) cerr << #x << " : = " << endl;
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int, int> PII;
const int N = 200020;
const int M = 200010;
const int inf = 0x3f3f3f3f;
int a[N], b[N], sum[N];
int dp[2][5000010];
void solve()
{
	int n, stx, sty;
	cin >> n >> stx >> sty;
	vector<PII> a(n + 1);
	vector<PII> b(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> a[i].fir >> a[i].sec >> b[i].fir >> b[i].sec;
		a[i].fir -= stx;
		a[i].sec -= stx;
		b[i].fir -= sty;
		b[i].sec -= sty;
	}
	auto isin = [&](int x, int y, int inp) {
		if (a[inp].fir <= x && x <= a[inp].sec && b[inp].fir <= y &&
			y <= b[inp].sec) {
			return true;
		}
		return false;
	};
	vector<vector<int>> dp(n + 1, vector<int>(n + 1, inf));
	int ans = 0;
	int now = 1;
	dp[0][0] = 0;
	for (int i = 1; i <= n; i++) {
		if (dp[i - 1][0] != inf) {
			// cout << i << endl;
			now = dp[i - 1][0] + 1;
			while (!isin(i - 1, 0, now) && now <= n) {
				now++;
			}
			if (now == n + 1)
				break;
			dp[i][0] = now;
			ans = max(ans, i);
			// cout << i << " " << now << endl;
		}
	}
	// cout << ans << endl;
	for (int i = 1; i <= n; i++) {
		if (dp[0][i - 1] != inf) {
			now = dp[0][i - 1] + 1;
			while (!isin(0, i - 1, now) && now <= n) {
				now++;
			}
			if (now == n + 1)
				break;
			dp[0][i] = now;
			ans = max(ans, i);
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; i + j <= n; j++) {
			if (dp[i - 1][j] != inf) {
				now = dp[i - 1][j] + 1;
				while (!isin(i - 1, j, now) && now <= n) {
					now++;
				}
				if (now != n + 1) {
					dp[i][j] = min(dp[i][j], now);
					ans = max(ans, i + j);
				}
			}

			if (dp[i][j - 1] != inf) {
				now = dp[i][j - 1];
				while (!isin(i, j - 1, now) && now <= n) {
					now++;
				}
				if (now != n + 1) {
					dp[i][j] = min(dp[i][j], now);
					ans = max(ans, i + j);
				}
			}
		}
	}

	cout << ans << endl;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T = 1;
	// cin >> T;
	while (T--) {
		solve();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3560kb

input:

22 2
N??A??????C???????????

output:

0

result:

wrong answer illegal char