oj.uz

답안 #842660

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
842660 2023-09-03T07:59:06 Z TheLostCookie 축구 경기장 (IOI23_soccer) C++17
30 / 100
 1 ms 600 KB 
#include "soccer.h"
#include <tuple>

struct SparseTable {
	std::vector<std::vector<int>> t;
	SparseTable(std::vector<int> v) {
		int n = v.size();
		int lg = (n==1?1:(32-__builtin_clz(n-1)));
		t.push_back(v);
		t.resize(lg+1);
		for(int i = 1; i <= lg; i++) {
			t[i].resize(n);
			for(int j = 0; j <= n-(1<<i); j++) {
				t[i][j] = std::max(t[i-1][j],t[i-1][j+(1<<i)]);
			}
		}
	};
	
	//[l,r)
	int query(int l, int r) {
		if(l+1==r) return t[0][l];
		int lg = (31-__builtin_clz(r-l-1));
		return std::max(t[lg][l],t[lg][r-(1<<lg)]);
	}
};

int biggest_stadium(int N, std::vector<std::vector<int>> F) {
	int R = 1;
	while(4*(R+1)*(R+1) <= N) R++;
	
	int ans = 0;
	//Phase 1: Precalculate small segments
	//[x][y][len] = {top,bottom,prec value}
	std::vector<std::vector<std::vector<std::tuple<int,int,int>>>> prec(N,std::vector<std::vector<std::tuple<int,int,int>>>(N,std::vector<std::tuple<int,int,int>>(R+1)));
	for(int y = 0; y < N; y++) {
		for(int x0=0,x1; x0<N; x0=x1+1) {
			x1=x0;
			if(F[x0][y]) prec[x0][y][1] = std::make_tuple(x0,x1,0);
			else {
				while(x1<N-1&&!F[x1+1][y]) x1++;
				for(int i = x0; i <= x1; i++) {
					prec[i][y][1] = std::make_tuple(x0,x1,x1-x0+1);
					ans = std::max(ans,std::get<2>(prec[i][y][1]));
				}
			}
		}
	}
	
	for(int len = 2; len <= R; len++) {
		for(int x = 0; x <= N-len; x++) {
			for(int y = 0; y < N; y++) {
				prec[x][y][len] = std::make_tuple(x,x,0);
				auto [u0,d0,v0] = prec[x][y][len-1];
				auto [u1,d1,v1] = prec[x+1][y][len-1];
				int u = std::max(u0,u1), d = std::min(d0,d1);
				if(v0 && v1) {
					prec[x][y][len] = std::make_tuple(u,d,std::max(v0,v1)+(u-d+1));
					ans = std::max(ans,std::get<2>(prec[x][y][len]));
				}
			}
		}
	}
	
	std::vector<SparseTable> st;
	for(int x = 0; x < N; x++) {
		std::vector<int> v;
		for(int y = 0; y < N; y++) v.push_back(std::get<2>(prec[x][y][R]));
		st.emplace_back(v);
	}
	
	//Phase 2: DP large segments
	//[x] = {left,right,dp value}, filter out all 
	std::vector<std::vector<std::tuple<int,int,int>>> dp(N);
	for(int x = 0; x < N; x++) {
		for(int y0=0,y1; y0 < N; y0=y1+1) {
			y1=y0;
			if(!F[x][y0]) {
				while(y1<N-1&&!F[x][y1+1]) y1++;
				if(y1-y0+1>R) {
					dp[x].emplace_back(y0,y1,y1-y0+1);
					ans = std::max(ans,std::get<2>(dp[x].back())+st[x].query(y0,y1-R+2)-R);
				}
			}
		}
	}
	
	for(int h = 2; h <= N; h++) {
		std::vector<std::vector<std::tuple<int,int,int>>> nxt(N-h+1);
		for(int x=0; x<=N-h; x++) {
			int i0=0,i1=0;
			while(i0<int(dp[x].size())&&i1<int(dp[x+1].size())) {
				auto [l0,r0,v0] = dp[x][i0];
				auto [l1,r1,v1] = dp[x+1][i1];
				if(r0 < l1) i0++;
				else if(r1 < l0) i1++;
				else {
					int l = std::max(l0,l1), r = std::min(r0,r1);
					if(r-l+1 <= R) {
						ans = std::max(ans,std::max(v0,v1)+std::get<2>(prec[x][l][r-l+1])-(h-1)*(r-l+1));
					} else {
						nxt[x].emplace_back(l,r,std::max(v0,v1)+(r-l+1));
						ans = std::max(ans,std::get<2>(nxt[x].back())+st[x].query(l,r-R+2)-h*R);
					}
					
					if(r0<r1) i0++;
					else i1++;
				}
			}
		}
		swap(nxt,dp);
	}
	for(auto [l,r,v]: dp[0]) {
		ans = std::max(ans,v);
	}
	
	return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 420 KB ok
3 Correct 0 ms 348 KB ok
4 Incorrect 0 ms 424 KB wrong
5 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 420 KB ok
4 Correct 0 ms 348 KB ok
5 Incorrect 0 ms 424 KB wrong
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 420 KB ok
4 Correct 0 ms 348 KB ok
5 Incorrect 0 ms 424 KB wrong
6 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 420 KB ok
4 Correct 0 ms 348 KB ok
5 Incorrect 0 ms 424 KB wrong
6 Halted 0 ms 0 KB -