Submission #842682

#	Time	Username	Problem	Language	Result	Execution time	Memory
842682		TheLostCookie	Soccer Stadium (IOI23_soccer)	C++17	100 / 100	3496 ms	1448532 KiB

soccer

#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-1))]);
			}
		}
	};
	
	//[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; x++) {
			for(int y = 0; y <= N-len; 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][y+1][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)+(d-u+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
• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 22 / 22
• Subtask 4: 18 / 18
• Subtask 5: 16 / 16
• Subtask 6: 30 / 30