제출 #777646

#제출 시각아이디문제언어결과실행 시간메모리
777646serkanrashidNafta (COI15_nafta)C++14
11 / 100
1091 ms3540 KiB
#include <bits/stdc++.h> #define endl "\n" using namespace std; struct Point { int x,y; Point(){}; Point(int xi, int yi) { x = xi; y = yi; } Point operator+(Point ed) { Point res; res.x = x + ed.x; res.y = y + ed.y; return res; } }; const int maxn = 2005; int n,m; int a[maxn][maxn],used[maxn][maxn]; bool vis[maxn*maxn]; long long sum[maxn*maxn]; Point dir[4] = {{1,0},{-1,0},{0,1},{0,-1}}; vector<long long>dp_bef,dp_cur; long long ans; int idx; void read() { cin >> n >> m; char z; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin >> z; if(z=='.') used[i][j] = -1; else a[i][j] = z-'0'; } } for(int i=0;i<=n+1;i++) used[i][0] = used[i][m+1] = -1; for(int j=0;j<=m+1;j++) used[0][j] = used[n+1][j] = -1; } void dfs(Point beg) { used[beg.x][beg.y] = idx; sum[idx] += a[beg.x][beg.y]; Point nb; for(int i=0;i<4;i++) { nb = beg + dir[i]; if(!used[nb.x][nb.y]) dfs(nb); } } void pre() { for(int j=1;j<=m;j++) { for(int i=1;i<=n;i++) { if(!used[i][j]) { idx++; dfs({i,j}); } } } dp_bef.clear(); dp_cur.clear(); dp_bef.resize(m+1); dp_cur.resize(m+1); } long long cost(int l, int r) { long long oil = 0; for(int i=1;i<=n;i++) { if(used[i][l]==-1) continue; vis[used[i][l]] = 1; } for(int i=1;i<=n;i++) { if(used[i][r]==-1) continue; if(!vis[used[i][r]]) oil += sum[used[i][r]]; vis[used[i][r]] = 1; } for(int i=1;i<=n;i++) { if(used[i][l]!=-1) vis[used[i][l]] = 0; if(used[i][r]!=-1) vis[used[i][r]] = 0; } return oil; } void divide(int l, int r, int optl, int optr) { if(l>r) return; int mid = (l+r)/2; pair<long long, int> best = {0,-1}; for(int i=optl;i<=min(mid,optr);i++) { long long pom = dp_bef[i] + cost(i,mid); if(pom>best.first) best = {pom,i}; } dp_cur[mid] = best.first; ans = max(ans,dp_cur[mid]); int opt = best.second; divide(l,mid-1,optl,opt); divide(mid+1,r,opt,optr); } void solve() { pre(); for(int i=1;i<=m;i++) { dp_bef[i] = cost(0,i); ans = max(ans,dp_bef[i]); } cout << ans << endl; for(int j=2;j<=m;j++) { divide(1,m,1,m); dp_bef = dp_cur; cout << ans << endl; } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); read(); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...