QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#163896#7120. Soccerzhouhuanyi0 279ms168640kbC++141.2kb2023-09-04 16:18:362023-09-04 16:18:37

Judging History

你现在查看的是测评时间为 2023-09-04 16:18:37 的历史记录

  • [2024-04-28 07:05:19]
  • 管理员手动重测本题所有提交记录
  • 测评结果:0
  • 用时:273ms
  • 内存:167612kb
  • [2023-09-04 16:18:37]
  • 评测
  • 测评结果:0
  • 用时:279ms
  • 内存:168640kb
  • [2023-09-04 16:18:36]
  • 提交

answer

#include"soccer.h"
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 3000
using namespace std;
const int inf=(int)(1e9);
int n,ans,R[N+1][N+1],dp[N+1][N+1],ls[N+1],rs[N+1],fa[N+1][N+1],l[N+1][N+1],r[N+1][N+1],dque[N+1],top;
bool used[N+1][N+1];
int calc(int x,int y)
{
	if (R[x][y]==y-1) return -inf;
	if (used[x][y]) return dp[x][y];
	int res=r[y][x]-l[y][x]+1;
	if (y+1<=n) res=max(res,calc(x,y+1)+r[y][x]-l[y][x]+1);
	if (fa[y][x]) res=max(res,calc(fa[y][x],y));
	used[x][y]=1,dp[x][y]=res;
	return res;
}
int biggest_stadium(int SN,vector<vector<int>>F)
{
	n=SN;
	for (int i=1;i<=n;++i) R[i][n+1]=n;
	for (int i=1;i<=n;++i)
		for (int j=n;j>=1;--j)
		{
			if (!F[i-1][j-1]) R[i][j]=R[i][j+1];
			else R[i][j]=j-1;
		}
	for (int i=1;i<=n;++i)
	{
		top=0;
		for (int j=1;j<=n;++j) ls[j]=rs[j]=0;
		for (int j=1;j<=n;++j)
		{
		    while (top&&R[dque[top]][i]>=R[j][i]) ls[j]=dque[top],top--;
			if (top) rs[dque[top]]=j;
			l[i][j]=dque[top]+1,dque[++top]=j;
		}
		for (int j=n;j>=1;--j)
		{
			if (ls[j]) fa[i][ls[j]]=j;
			if (rs[j]) fa[i][rs[j]]=j;
			if (rs[j]) r[i][j]=r[i][rs[j]];
			else r[i][j]=j;
		}
	}
	for (int i=1;i<=n;++i)
		for (int j=1;j<=n;++j)
			ans=max(ans,calc(i,j));
	return ans;
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 6
Accepted
time: 3ms
memory: 9960kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
1
0

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
1

result:

ok ok

Test #2:

score: 6
Accepted
time: 2ms
memory: 12308kb

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: 1ms
memory: 16912kb

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
9700

result:

points 0.250 partial

Test #4:

score: 6
Accepted
time: 17ms
memory: 44108kb

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: 279ms
memory: 168640kb

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: 2ms
memory: 12064kb

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: 2ms
memory: 12360kb

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
90

result:

wrong answer wrong

Subtask #2:

score: 0
Wrong Answer

Test #10:

score: 2
Acceptable Answer
time: 2ms
memory: 11988kb

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: 2ms
memory: 12028kb

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: 2ms
memory: 12060kb

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: 0ms
memory: 14060kb

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: 0ms
memory: 12104kb

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: 2ms
memory: 12040kb

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%