QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#292435 | #7120. Soccer | Feet_McYeet | 0 | 2623ms | 2019188kb | C++17 | 3.9kb | 2023-12-28 04:59:57 | 2024-04-28 08:03:52 |
Judging History
answer
// #include "closing.h"
#include <bits/stdc++.h>
using namespace std;
// #pragma GCC optimize ("Ofast")
// #pragma GCC target ("avx2")
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
#define el << '\n'
#define nl cout << '\n'
#define spc << ' '
#define forn(i,n) for (int i=0; i<n; i++)
#define forl(i,s,e) for (int i=s; i<e; i++)
#define pb push_back
#define fi first
#define se second
#define rsz resize
#define sz(x) ((int) x.size())
#define all(x) x.begin(), x.end()
const int inf = 1000000000;
const ll inf2 = 4000000000000000000;
// 0 -> (1, 0), down
// 1 -> (0, 1), right
// 2 -> (-1, 0), up
// 3 -> (0, -1), left
const int MAXN = 2005;
int n;
bool f[MAXN][MAXN];
int nt[MAXN][MAXN][4];
int lg(int k) {
return 32-__builtin_clz(k);
}
void smax(int& a, int b) {
if (b>a) a=b;
}
void gnt() {
forn(i,n) {
int lp[4] = {n, n, -1, -1};
forn(j,n) {
if (f[i][j]) lp[3] = j;
if (f[j][i]) lp[2] = j;
nt[i][j][3] = lp[3];
nt[j][i][2] = lp[2];
}
for (int j = n-1; j>=0; j--) {
if (f[i][j]) lp[1] = j;
if (f[j][i]) lp[0] = j;
nt[i][j][1] = lp[1];
nt[j][i][0] = lp[0];
}
}
}
vector<pii> st[MAXN][MAXN][4];
void gst() {
forn(i,n) {
for (int j = n-1; j>=0; j--) {
int l = lg(n-j);
st[i][j][0].rsz(l);
st[j][i][1].rsz(l);
st[i][j][2].rsz(l);
st[j][i][3].rsz(l);
st[i][j][0][0] = {nt[i][j][0], j};
st[j][i][1][0] = {nt[j][i][1], j};
st[i][j][2][0] = {nt[i][j][2], j};
st[j][i][3][0] = {nt[j][i][3], j};
forl(js, 1, l) {
int dt = j + (1<<(js-1));
st[i][j][0][js] = min(st[i][j][0][js-1], st[i][dt][0][js-1]);
st[j][i][1][js] = min(st[j][i][1][js-1], st[dt][i][1][js-1]);
st[i][j][2][js] = max(st[i][j][2][js-1], st[i][dt][2][js-1]);
st[j][i][3][js] = max(st[j][i][3][js-1], st[dt][i][3][js-1]);
}
}
}
}
pii rq(int x, int y1, int y2, int qt) {
int l = lg(y2-y1)-1;
int y3 = y2 - (1<<l) + 1;
if (qt==0) return min(st[x][y1][0][l], st[x][y3][0][l]);
if (qt==1) return min(st[y1][x][1][l], st[y3][x][1][l]);
if (qt==2) return max(st[x][y1][2][l], st[x][y3][2][l]);
return max(st[y1][x][3][l], st[y3][x][3][l]);
}
int dp[MAXN][MAXN];
int rb[MAXN][MAXN][4];
void gr() {
forn(i,n) {
forn(j,n) {
if (f[i][j]) {
rb[i][j][0] = -1;
continue;
}
rb[i][j][3] = j;
int k = nt[i][j][1] - 1;
rb[i][j][1] = k;
rb[i][j][0] = rq(i, j, k, 0).fi-1;
rb[i][j][2] = rq(i, j, k, 2).fi+1;
// cout << i spc << j spc spc << rb[i][j][0] spc << rb[i][j][1] spc << rb[i][j][2] spc << rb[i][j][3] el;
}
}
}
struct rt{
int x, y, w;
};
bool operator < (const rt& r1, const rt& r2) {
return r1.w < r2.w;
}
int solve() {
vector<rt> oo;
forn(i,n) forn(j,n) if (rb[i][j][0] != -1) oo.pb({i, j, rb[i][j][1] - rb[i][j][3] + 1});
sort(all(oo));
int ans = 0;
for (rt i : oo) {
if (dp[i.x][i.y] == 0) dp[i.x][i.y] = (rb[i.x][i.y][0] - rb[i.x][i.y][2] + 1) * i.w;
// cout << i.x spc << i.y spc << dp[i.x][i.y] el;
smax(ans, dp[i.x][i.y]);
if (i.y && !f[i.x][i.y-1]) smax(dp[i.x][i.y-1], dp[i.x][i.y] + rb[i.x][i.y-1][0] - rb[i.x][i.y-1][2] + 1);
if (i.x != rb[i.x][i.y][2]) {
int v = rq(i.y, rb[i.x][i.y][2], i.x-1, 1).se;
smax(dp[v][i.y], dp[i.x][i.y] + (rb[v][i.y][0] - rb[v][i.y][2]) * (rb[v][i.y][1] - rb[i.x][i.y][1]));
}
if (i.x != rb[i.x][i.y][0]) {
int v = rq(i.y, i.x+1, rb[i.x][i.y][0], 1).se;
smax(dp[v][i.y], dp[i.x][i.y] + (rb[v][i.y][0] - rb[v][i.y][2]) * (rb[v][i.y][1] - rb[i.x][i.y][1]));
}
}
// nl;
// forn(i,n) {
// forn(j,n) cout << dp[i][j] spc;
// nl;
// }
return ans;
}
int biggest_stadium(int N, vector<vector<int>> F) {
n = N;
forn(i,n) forn(j,n) f[i][j] = F[i][j];
gnt();
// forn(i,4) {
// forn(j,n) {
// forn(k, n) cout << nt[j][k][i] spc;
// nl;
// }
// nl;
// }
gst();
gr();
return solve();
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 6
Accepted
time: 61ms
memory: 384716kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 1 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 1
result:
ok ok
Test #2:
score: 6
Accepted
time: 47ms
memory: 387100kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 0 0 1 0 0 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 5
result:
ok ok
Test #3:
score: 1.5
Acceptable Answer
time: 51ms
memory: 394312kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 100 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 9847
result:
points 0.250 partial
Test #4:
score: 6
Accepted
time: 188ms
memory: 497996kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 500 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 236536
result:
ok ok
Test #5:
score: 6
Accepted
time: 2623ms
memory: 2019188kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 2000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 3786181
result:
ok ok
Test #6:
score: 6
Accepted
time: 47ms
memory: 384812kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 9 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 80
result:
ok ok
Test #7:
score: 0
Wrong Answer
time: 73ms
memory: 384800kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 10 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 98
result:
wrong answer wrong
Subtask #2:
score: 0
Wrong Answer
Test #10:
score: 2
Acceptable Answer
time: 52ms
memory: 384792kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 0 0 1 0 0 1 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 4
result:
points 0.250 partial
Test #11:
score: 2
Acceptable Answer
time: 48ms
memory: 385044kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 0 0 1 1 0 0 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 3
result:
points 0.250 partial
Test #12:
score: 2
Acceptable Answer
time: 40ms
memory: 385016kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 1 0 0 0 1 1 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 4
result:
points 0.250 partial
Test #13:
score: 8
Accepted
time: 56ms
memory: 384756kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 1 0 0 1 0 1 0 0 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 4
result:
ok ok
Test #14:
score: 2
Acceptable Answer
time: 56ms
memory: 384736kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 1 0 0 0 1 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 5
result:
points 0.250 partial
Test #15:
score: 0
Wrong Answer
time: 44ms
memory: 384788kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 1 0 0 1 0 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 6
result:
wrong answer wrong
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%