QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#546301 | #8776. Not Another Constructive! | Djangle162857 | WA | 0ms | 3560kb | C++20 | 2.2kb | 2024-09-03 22:36:53 | 2024-09-03 22:36:54 |
Judging History
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();
}
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3560kb
input:
22 2 N??A??????C???????????
output:
0
result:
wrong answer illegal char