| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 931181 | dosts | Nafta (COI15_nafta) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define sp << " " <<
//#define int long long
#define ff first
#define ss second
#define vi vector<int>
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
template<typename T1, typename T2> bool MIN(T1 &a, T2 b){return a > b ? a = b, true : false;}
template<typename T1, typename T2> bool MAX(T1 &a, T2 b){return a < b ? a = b, true : false;}
const int N = 2e3+2,inf = 2e18;
pii dad[N][N];
int sm[N][N];
pii find(int x,int y) {
if (pii{x,y} == dad[x][y]) return dad[x][y];
return dad[x][y] = find(dad[x][y].first,dad[x][y].second);
}
void unite(int x1,int y1,int x2,int y2) {
sm[find(x2,y2).first][find(x2,y2).second]+=sm[find(x1,y1).first][find(x1,y1).second];
dad[find(x1,y1).first][find(x1,y1).second] = find(x2,y2);
}
int common[N][N];
int util[N];
int sag[N][N];
vector<pii> edges[N][N];
int vis[N][N];
void dfs(int x,int y,int z) {
if (vis[x][y]) return;
vis[x][y] = 1;
sag[x][y] = z;
for (auto it : edges[x][y]) dfs(it.first,it.second,z);
}
vi dp_prev(N,0),dp(N,0);
void dnc(int optl,int optr,int l,int r) {
if (l > r) return;
int m = (l+r) >> 1;
int opt = optl,best = 0;
for (int i=optl;i<=min(optr,m-1);i++) {
if (dp_prev[i]+util[m]-common[i][m] > best) {
best = dp_prev[i]+util[m]-common[i][m];
opt = i;
};
}
dp[m] = best;
dnc(optl,opt,l,m-1);
dnc(opt,optr,m+1,r);
}
void solve() {
int n,m;
cin >> n >> m;
for (int i=1;i<=m;i++) for (int j=1;j<=m;j++) common[i][j] = 0;
for (int i=1;i<=m;i++) util[i] = 0;
vector<vi> a(n+1,vi(m+1));
int dot = '.'-'0';
for (int i=1;i<=n;i++) {
string s;
cin >> s;
for (int j=1;j<=m;j++) {
if (s[j-1]>='0' && s[j-1] <= '9') {
a[i][j] = s[j-1]-'0';
}
else a[i][j] = -2;
}
}
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) dad[i][j] = {i,j},sm[i][j] = max(0ll,a[i][j]);
vi dx{1,0,-1,0},dy{0,1,0,-1};
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
if(a[i][j] == dot) continue;
for (int d = 0;d<4;d++) {
int gx = i+dx[d],gy = j+dy[d];
if (gx < 1 || gx > n || gy < 1 || gy > m) continue;
if (a[gx][gy] == dot) continue;
edges[i][j].push_back({gx,gy});
edges[gx][gy].push_back({i,j});
if (find(i,j) == find(gx,gy)) continue;
unite(i,j,gx,gy);
}
}
}
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) vis[i][j] = 0;
for (int i=m;i>=1;i--){
for (int j = 1;j<=n;j++) {
dfs(j,i,i);
}
}
int got[n+1][m+1];
memset(got,0,sizeof got);
for (int i=1;i<=m;i++) {
vector<pair<pii,int>> pushed;
for (int r=1;r<=n;r++) {
if (a[r][i] == dot) continue;
auto[x,y] = find(r,i);
pushed.push_back({{x,y},r});
}
for (auto itt : pushed) {
pii it = itt.first;
int r = itt.second;
if (got[it.first][it.second]) continue;
got[it.first][it.second] = 1;
util[i]+=sm[it.first][it.second];
common[i][i]+=sm[it.first][it.second];
common[i][sag[r][i]+1]-=sm[it.first][it.second];
}
for (auto it : pushed) if (got[it.ff.first][it.ff.second]) got[it.ff.first][it.ff.second] = 0;
}
for (int i=1;i<=m;i++) {
for (int j=i+1;j<=m;j++) common[i][j]+=common[i][j-1];
}
for (int i=1;i<=m;i++) {
for (int j=1;j<i;j++) common[i][j]= common[j][i];
}
for (int i=1;i<=m;i++) dp_prev[i] = util[i];
cout << *max_element(dp_prev.begin()+1,dp_prev.end()) << '\n';
for (int i=2;i<=m;i++) {
dnc(0,m,1,m);
cout << *max_element(dp.begin(),dp.end());
if(i != m) cout << '\n';
dp_prev = dp;
for (int j=1;j<=m;j++) dp[j] = 0;
}
}
signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Dodi
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t = 1;
//cin >> t;
while (t --> 0) solve();
}