Submission #906704

#	Time	Username	Problem	Language	Result	Execution time	Memory
906704		vjudge1	Council (JOI23_council)	C++17	0 / 100	70 ms	323688 KiB

council

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define F first
#define S second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

ll dp[3][2][2][151][151][151];

const ll mod = 1e9+7;

int n;
vector<string> g;
vector<vi> ps;

bool query(int a, int b, int x, int y){
	return (ps[x][y]-ps[x][b]-ps[a][y]+ps[a][b]) > 0;
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	cin>>n;
	g.resize(n);rep(i,0,n)cin>>g[i];
	ps.assign(n+1,vi(n+1,0));
	rep(i,0,n)rep(j,0,n){
		ps[i+1][j+1]=ps[i+1][j]+ps[i][j+1]-ps[i][j]+(g[i][j]=='.');
	}
	rep(ph,0,3)rep(b,0,2)rep(t,0,2)rep(i,0,151)rep(j,0,151)rep(k,0,151)dp[ph][b][t][i][j][k]=-1;
	function<ll(int,int,int,int,int,int)> solve = [&](int x, int yb, int yt, int b, int t, int ph) -> ll {
		if(ph>2) return 1;
		if(yb<0 || yb >= n) return 0;
		if(yt>n || yt <= 0) return 0;
		if(x>=n) return 0;
		if(ph==2 && (yb>=yt || query(x+1,yt,x,yb))) return 0;
		if(dp[ph][b][t][x][yb][yt]!=-1) return dp[ph][b][t][x][yb][yt];
		ll ans = solve(x,yb,yt,b,t,ph+1);
		if(ph == 0){ // modify yb
			(ans += solve(x,yb-(2*b-1),yt,b,t,ph))%=mod;
		}else if(ph == 1){ // modify yt
			(ans += solve(x,yb,yt+(2*t-1),b,t,ph))%=mod;
		}else if(ph == 2){ // modify x
			if(b){
				if(t) (ans+=solve(x+1,yb,yt,1,1,0))%=mod;
				(ans+=solve(x+1,yb,yt-t,1,0,0))%=mod;
				(ans+=mod-solve(x+1,0,yb,0,0,0))%=mod;
			}
			if(t) {
				(ans+=solve(x+1,yb+b,yt,0,1,0))%=mod;
				(ans+=mod-solve(x+1,yt,n,0,0,0))%=mod;
			}
			(ans+=solve(x+1,yb+b,yt-t,0,0,0))%=mod;
		}
		// cout<<ph<<' '<<b<<' '<<t<<' '<<x<<' '<<yb<<' '<<yt<<" = "<<ans<<endl;
		return dp[ph][b][t][x][yb][yt]=ans;
	};

	// cout<<solve(0,0,0+1,1,1,0)<<endl;
	// return 0;
	ll ans = 0;
	rep(i,0,n)rep(j,0,n){
		// if(g[i][j]=='G') cout<<i<<' '<<j<<' '<<solve(i,j,j+1,1,1,1)<<endl;
		(ans+=solve(i,j,j+1,1,1,1))%=mod;
	}
	cout<<ans<<endl;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 8
• Subtask 3: 0 / 6
• Subtask 4: 0 / 19
• Subtask 5: 0 / 15
• Subtask 6: 0 / 22
• Subtask 7: 0 / 22