QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#555792 | #8780. Training, Round 2 | chengning0909 | WA | 1ms | 5696kb | C++11 | 1.1kb | 2024-09-10 09:57:25 | 2024-09-10 09:57:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
int n, x, y, lx[N], rx[N], ly[N], ry[N], ans;
bitset<N> dp[2][N];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> x >> y;
for (int i = 1; i <= n; i++) {
cin >> lx[i] >> rx[i] >> ly[i] >> ry[i];
}
dp[0][0][0] = 1;
for (int i = 1; i <= n; i++) {
int k = i & 1;
for (int j = 0; j <= n; j++) {
dp[k][j] = dp[k ^ 1][j];
if (lx[i] <= x + j && x + j <= rx[i]) {
dp[k][j] |= (dp[k ^ 1][j] << 1) | (dp[k ^ 1][j - 1]);
}
}
if (0 <= ly[i] - y && ly[i] - y <= n && 0 <= ry[i] - y && ry[i] - y <= n) {
int l = ly[i] - y, r = ry[i] - y;
for (int j = 0; j <= n; j++) {
dp[k][j] = (dp[k][j] >> l) << l;
dp[k][j] = (dp[k][j] << (n - r)) >> (n - r);
}
}
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
if (dp[n & 1][i][j]) ans = max(ans, i + j);
}
}
cout << ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 5696kb
input:
3 0 0 0 1 0 1 1 1 0 1 1 1 1 1
output:
4
result:
wrong answer 1st lines differ - expected: '3', found: '4'