답안 #842739

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
842739	2023-09-03T10:27:53 Z	errorgorn	축구 경기장 (IOI23_soccer)	C++17	64 / 100	4500 ms	95776 KB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ii pair<int,int>
#define iii pair<ii,int>
#define fi first
#define se second
#define endl '\n'

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n;
int arr[2005][2005];

vector<ii> V;

vector<ii> L[2005],R[2005];
int memo[2005][2005];

void dfs(int x,vector<ii> v,int d){
	if (x==-1 || x==n) return;
	
	vector<ii> res;
	for (auto [l,r]:v){
		rep(y,l,r+1) if (arr[x][y]==0){
			if (!res.empty() && res.back().se+1==y) res.back().se++;
			else res.pub({y,y});
		}
	}
	
	for (auto it:res) V.pub(it);
	
	dfs(x+d,res,d);
}

signed biggest_stadium(signed N, std::vector<std::vector<signed>> F){
	n=N;
	rep(x,0,n) rep(y,0,n) arr[x][y]=F[x][y];
	
	int ans=0;
	rep(x,0,n){
		vector<ii> v;
		rep(y,0,n) if (arr[x][y]==0){
			if (!v.empty() && v.back().se+1==y) v.back().se++;
			else v.pub({y,y});
		}
		
		V=v;
		dfs(x-1,v,-1);
		dfs(x+1,v,1);
		
		sort(all(V),[](ii i,ii j){
			if ((i.se-i.fi)==(j.se-j.fi)) return i>j;
			else return i.se-i.fi<j.se-j.fi;
		});
		vector<iii> res;
		for (auto it:V){
			if (!res.empty() && res.back().fi==it) res.back().se++;
			else res.pub({it,1});
		}
		
		//for (auto it:res) cout<<it.fi.fi<<" "<<it.fi.se<<" "<<it.se<<endl;
		//cout<<endl;
		
		rep(x,0,n) L[x].clear(),R[x].clear();
		
		for (auto it:res){
			L[it.fi.fi].pub({it.fi.se,it.se});
			R[it.fi.se].pub({it.fi.fi,it.se});
		}
		
		rep(x,0,n+1) rep(y,x,n+1) memo[x][y]=0;
		rep(l,0,n+1) rep(x,0,n-l+1){
			int y=x+l;
			if (x!=0){
				int t=memo[x][y];
				for (auto it:L[x]) if (y<=it.fi) t+=(min(it.fi,y)-x+1)*it.se;
				memo[x-1][y]=max(memo[x-1][y],t);
			}
			if (y!=n){
				int t=memo[x][y];
				for (auto it:R[y]) if (it.fi<=x) t+=(y-max(it.fi,x)+1)*it.se;
				memo[x][y+1]=max(memo[x][y+1],t);
			}
		}
		
		ans=max(ans,memo[0][n]);
		//rep(x,0,n+1){
			//rep(y,0,n+1) cout<<memo[x][y]<<" "; cout<<endl;
		//}
		//cout<<endl;
	}
	
	return ans;
}

Subtask #0
0.0 / 0.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2392 KB	ok

Subtask #1
0.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2396 KB	ok
2	Correct	1 ms	2396 KB	ok
3	Correct	1 ms	2396 KB	ok
4	Correct	1 ms	2396 KB	ok
5	Correct	1 ms	2392 KB	ok
6	Correct	1 ms	2392 KB	ok
7	Correct	7 ms	7004 KB	ok
8	Correct	531 ms	21140 KB	ok
9	Execution timed out	4576 ms	95776 KB	Time limit exceeded
10	Halted	0 ms	0 KB	-

Subtask #2
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2396 KB	ok
2	Correct	1 ms	2396 KB	ok
3	Correct	1 ms	2648 KB	ok
4	Correct	1 ms	2392 KB	ok
5	Correct	1 ms	2396 KB	ok
6	Correct	1 ms	2396 KB	ok
7	Correct	0 ms	2396 KB	ok
8	Correct	1 ms	2392 KB	ok
9	Correct	1 ms	2396 KB	ok
10	Correct	1 ms	2392 KB	ok
11	Correct	1 ms	2396 KB	ok
12	Correct	1 ms	2396 KB	ok
13	Correct	0 ms	2392 KB	ok

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2392 KB	ok
2	Correct	1 ms	2396 KB	ok
3	Correct	1 ms	2396 KB	ok
4	Correct	1 ms	2648 KB	ok
5	Correct	1 ms	2392 KB	ok
6	Correct	1 ms	2396 KB	ok
7	Correct	1 ms	2396 KB	ok
8	Correct	0 ms	2396 KB	ok
9	Correct	1 ms	2392 KB	ok
10	Correct	1 ms	2396 KB	ok
11	Correct	1 ms	2392 KB	ok
12	Correct	1 ms	2396 KB	ok
13	Correct	1 ms	2396 KB	ok
14	Correct	0 ms	2392 KB	ok
15	Correct	1 ms	2392 KB	ok
16	Correct	1 ms	2392 KB	ok
17	Correct	1 ms	2392 KB	ok
18	Correct	1 ms	2392 KB	ok
19	Correct	1 ms	2448 KB	ok
20	Correct	1 ms	2392 KB	ok
21	Correct	1 ms	2392 KB	ok
22	Correct	1 ms	2392 KB	ok
23	Correct	1 ms	2392 KB	ok
24	Correct	1 ms	2392 KB	ok
25	Correct	0 ms	2396 KB	ok
26	Correct	1 ms	2392 KB	ok

Subtask #4
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2392 KB	ok
2	Correct	1 ms	2396 KB	ok
3	Correct	1 ms	2396 KB	ok
4	Correct	1 ms	2396 KB	ok
5	Correct	1 ms	2396 KB	ok
6	Correct	1 ms	2648 KB	ok
7	Correct	1 ms	2392 KB	ok
8	Correct	1 ms	2396 KB	ok
9	Correct	1 ms	2396 KB	ok
10	Correct	0 ms	2396 KB	ok
11	Correct	1 ms	2392 KB	ok
12	Correct	1 ms	2396 KB	ok
13	Correct	1 ms	2392 KB	ok
14	Correct	1 ms	2396 KB	ok
15	Correct	1 ms	2396 KB	ok
16	Correct	0 ms	2392 KB	ok
17	Correct	1 ms	2392 KB	ok
18	Correct	1 ms	2392 KB	ok
19	Correct	1 ms	2392 KB	ok
20	Correct	1 ms	2392 KB	ok
21	Correct	1 ms	2448 KB	ok
22	Correct	1 ms	2392 KB	ok
23	Correct	1 ms	2392 KB	ok
24	Correct	1 ms	2392 KB	ok
25	Correct	1 ms	2392 KB	ok
26	Correct	1 ms	2392 KB	ok
27	Correct	0 ms	2396 KB	ok
28	Correct	1 ms	2392 KB	ok
29	Correct	1 ms	2392 KB	ok
30	Correct	1 ms	4440 KB	ok
31	Correct	1 ms	4444 KB	ok
32	Correct	1 ms	4444 KB	ok
33	Correct	1 ms	4440 KB	ok
34	Correct	1 ms	4440 KB	ok
35	Correct	1 ms	4440 KB	ok
36	Correct	1 ms	4444 KB	ok
37	Correct	1 ms	4440 KB	ok
38	Correct	1 ms	4440 KB	ok
39	Correct	1 ms	4444 KB	ok
40	Correct	1 ms	4440 KB	ok
41	Correct	1 ms	4440 KB	ok

Subtask #5
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2392 KB	ok
2	Correct	1 ms	2396 KB	ok
3	Correct	1 ms	2396 KB	ok
4	Correct	1 ms	2396 KB	ok
5	Correct	1 ms	2396 KB	ok
6	Correct	1 ms	2648 KB	ok
7	Correct	1 ms	2392 KB	ok
8	Correct	1 ms	2396 KB	ok
9	Correct	1 ms	2396 KB	ok
10	Correct	0 ms	2396 KB	ok
11	Correct	1 ms	2392 KB	ok
12	Correct	1 ms	2396 KB	ok
13	Correct	1 ms	2392 KB	ok
14	Correct	1 ms	2396 KB	ok
15	Correct	1 ms	2396 KB	ok
16	Correct	0 ms	2392 KB	ok
17	Correct	1 ms	2392 KB	ok
18	Correct	1 ms	2392 KB	ok
19	Correct	1 ms	2392 KB	ok
20	Correct	1 ms	2392 KB	ok
21	Correct	1 ms	2448 KB	ok
22	Correct	1 ms	2392 KB	ok
23	Correct	1 ms	2392 KB	ok
24	Correct	1 ms	2392 KB	ok
25	Correct	1 ms	2392 KB	ok
26	Correct	1 ms	2392 KB	ok
27	Correct	0 ms	2396 KB	ok
28	Correct	1 ms	2392 KB	ok
29	Correct	1 ms	2392 KB	ok
30	Correct	1 ms	4440 KB	ok
31	Correct	1 ms	4444 KB	ok
32	Correct	1 ms	4444 KB	ok
33	Correct	1 ms	4440 KB	ok
34	Correct	1 ms	4440 KB	ok
35	Correct	1 ms	4440 KB	ok
36	Correct	1 ms	4444 KB	ok
37	Correct	1 ms	4440 KB	ok
38	Correct	1 ms	4440 KB	ok
39	Correct	1 ms	4444 KB	ok
40	Correct	1 ms	4440 KB	ok
41	Correct	1 ms	4440 KB	ok
42	Correct	1409 ms	21316 KB	ok
43	Correct	1173 ms	21348 KB	ok
44	Correct	2673 ms	23164 KB	ok
45	Correct	3150 ms	23828 KB	ok
46	Correct	1739 ms	22024 KB	ok
47	Correct	659 ms	21356 KB	ok
48	Correct	547 ms	21116 KB	ok
49	Correct	547 ms	21100 KB	ok
50	Correct	3843 ms	27020 KB	ok
51	Correct	512 ms	21480 KB	ok
52	Correct	388 ms	21056 KB	ok
53	Correct	343 ms	21076 KB	ok
54	Correct	379 ms	21264 KB	ok
55	Correct	437 ms	21328 KB	ok
56	Correct	400 ms	21084 KB	ok
57	Correct	628 ms	23020 KB	ok
58	Correct	638 ms	24912 KB	ok
59	Correct	645 ms	24912 KB	ok

Subtask #6
0.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2392 KB	ok
2	Correct	1 ms	2396 KB	ok
3	Correct	1 ms	2396 KB	ok
4	Correct	1 ms	2396 KB	ok
5	Correct	1 ms	2396 KB	ok
6	Correct	1 ms	2392 KB	ok
7	Correct	1 ms	2392 KB	ok
8	Correct	7 ms	7004 KB	ok
9	Correct	531 ms	21140 KB	ok
10	Execution timed out	4576 ms	95776 KB	Time limit exceeded
11	Halted	0 ms	0 KB	-

답안 #842739

Compilation message

Subtask #0 0.0 / 0.0

Subtask #1 0.0 / 6.0

Subtask #2 8.0 / 8.0

Subtask #3 22.0 / 22.0

Subtask #4 18.0 / 18.0

Subtask #5 16.0 / 16.0

Subtask #6 0.0 / 30.0

Subtask #0
0.0 / 0.0

Subtask #1
0.0 / 6.0

Subtask #2
8.0 / 8.0

Subtask #3
22.0 / 22.0

Subtask #4
18.0 / 18.0

Subtask #5
16.0 / 16.0

Subtask #6
0.0 / 30.0