Submission #1198523

#TimeUsernameProblemLanguageResultExecution timeMemory
1198523MuhammadSaramNafta (COI15_nafta)C++20
34 / 100
1097 ms25820 KiB
#include <bits/stdc++.h> using namespace std; const int M = 2001; int dp[M][M],col[M][M],com[M][M],sz[M*M],cc,n,m; string a[M]; void dfs(int i,int j) { col[i][j]=cc,sz[cc]+=a[i][j]-'0'; for (int px=-1;px<=1;px++) for (int py=-1;py<=1;py++) { if ((px==0)==(py==0)) continue; int ni=i+px,nj=j+py; if (min(ni,nj)>=0 && ni<n && nj<m && !col[ni][nj] && a[ni][nj]!='.') dfs(ni,nj); } } int main() { cin>>n>>m; for (int i=0;i<n;i++) cin>>a[i]; for (int i=0;i<n;i++) for (int j=0;j<m;j++) if (a[i][j]!='.' && !col[i][j]) cc++,dfs(i,j); for (int j=0;j<m;j++) { set<int> se; for (int i=0;i<n;i++) se.insert(col[i][j]); for (int j1=j;j1<m;j1++) { set<int> se1; for (int i=0;i<n;i++) if (col[i][j1] && !se1.count(col[i][j1]) && se.count(col[i][j1])) com[j][j1]+=sz[col[i][j1]],se1.insert(col[i][j1]); } } dp[0][1]=com[0][0]; for (int i=1;i<m;i++) for (int k=1;k<=m;k++) { dp[i][k]=dp[i-1][k]; for (int j=i-1;j>=0;j--) dp[i][k]=max(dp[i][k],com[i][i]+dp[j][k-1]-com[j][i]*(k>1)); } for (int i=1;i<=m;i++) cout<<dp[m-1][i]<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...