Submission #562231

#	Time	Username	Problem	Language	Result	Execution time	Memory
562231		Koosha_mv	Raspad (COI17_raspad)	C++14	100 / 100	2286 ms	9812 KiB

raspad

#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=1e5+99,M=52;

int n,m,a[N],col[M],Max1[M],Max2[M],dp[2][M][M];
ll ans;
string S[N];
vector<pair<int,int>> vec[2];

int32_t main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n>>m;
	f(i,1,n+1) cin>>S[i],S[i]=' '+S[i];
	f(id,1,n+1){
		string s=S[id];
		int t=id&1;
		iota(col,col+M,0);
		vec[t].clear();
		f(i,1,m+1) f(j,i+1,m+1) dp[t][i][j]=0;
		f(i,1,m+1){
			if(s[i]=='0') continue ;
			if(s[i-1]=='1'){
				col[i]=col[i-1];
				for(int j=i-1;s[j]=='1';j--){
					dp[t][j][i]=id;
					vec[t].pb({j,i});
				}
			}
		}
		for(auto p : vec[t^1]){
			if(col[p.F]==col[p.S] || s[p.F]=='0' || s[p.S]=='0') continue ;
			vector<int> v0,v1;
 			f(i,1,m+1) if(col[i]==col[p.F]) v0.pb(i);
			f(i,1,m+1) if(col[i]==col[p.S]) v1.pb(i);
			for(auto u : v0){
				for(auto v : v1){
					int x=u,y=v;
					col[y]=col[p.F];
					if(x>y) swap(x,y);
					vec[t].pb({x,y});
					dp[t][x][y]=dp[t^1][p.F][p.S];
				}
			}
		}
		f(i,1,m+1) Max1[i]=0,Max2[i]=0,dp[t][i][i]=id;
		f(i,1,m+1){
			f(j,i,m+1){
				if(s[i]=='0' || s[j]=='0') continue ;
				if(i!=j) maxm(Max1[j],dp[t][i][j]);
				if(id<n && S[id+1][i]=='1') maxm(Max2[j],dp[t][i][j]);
				if(id<n && S[id+1][j]=='1') maxm(Max2[i],dp[t][i][j]);
			}
		}
		f(i,1,m+1){
			if(s[i]=='0') continue ;
			maxm(Max2[i],Max1[i]);
			ans+=id-Max1[i];
			ans+=1ll*(id-Max2[i])*(n-id);
		}
	}
	cout<<ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 17 / 17
• Subtask 3: 35 / 35
• Subtask 4: 39 / 39