이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
int const mxN = 2e3+5;
int n,m,k, a[mxN][mxN], dp[mxN][mxN], c = 0;
int inC[mxN][mxN], first_col[mxN*mxN], cost[mxN*mxN];
bool vis[mxN][mxN];
bool valid ( int i, int j ) {
if(i<0 || j<0 || i==n || j==m) return false;
if(a[i][j]==-1 || vis[i][j]) return false;
vis[i][j] = 1;
return true;
}
int dfs ( int i, int j) {
int ans = a[i][j];
inC[i][j] = c;
first_col[c] = min ( j, first_col[c] );
if( valid(i+1,j) ) ans+=dfs(i+1,j);
if( valid(i,j+1) ) ans+=dfs(i,j+1);
if( valid(i-1,j) ) ans+=dfs(i-1,j);
if( valid(i,j-1) ) ans+=dfs(i,j-1);
return ans;
}
void solve ( int l, int r, int indl , int indr, int sz ) {
if(l>r) return;
int mid = (l+r)/2, ind = mid, maxi = 0;
for(int i=indl; i<=min(indr, mid-1); i++) {
int ans = dp[i][sz-1];
set<int>st;
for(int h=0; h<n; h++){
if(a[h][mid]!=-1 && st.find(inC[h][mid])==st.end() && first_col[inC[h][mid]]>i ) { ans+= cost[inC[h][mid]];st.insert(inC[h][mid]); }
}
if(ans>maxi) {
maxi = ans;
ind = i;
}
}
dp[mid][sz] = maxi;
solve(l,mid-1, indl, ind, sz), solve(mid+1, r, ind, indr, sz);
}
signed main (){
cin>>n>>m;
for(int i=0; i<n; i++)
for(int j=0; j<m; j++) {
char x; cin>>x;
if(x=='.') a[i][j] = -1;
else a[i][j] = x-'0';
}
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
if(!vis[i][j] && a[i][j]>-1) {
vis[i][j] = 1;
c++;
first_col[c] = 1e9;
cost[c] = dfs(i,j);
}
for(int j=0; j<m; j++) {
set<int> st;
int ans = 0;
for(int i=0; i<n; i++) {
if(st.find(inC[i][j])==st.end() && a[i][j]>-1 ) { ans+=cost[inC[i][j]]; st.insert(inC[i][j]); }
}
dp[j][1] = ans;
//cout<<j<<' '<<dp[j][1]<<'\n';
}
for(int i=2; i<=m; i++) solve(0,m-1, 0, m-1, i);
for(int i=1; i<=m; i++) {
int maxi = 0;
for(int h=0; h<m; h++) maxi = max ( maxi, dp[h][i]);
cout<<maxi<<'\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |