Submission #1034570

#TimeUsernameProblemLanguageResultExecution timeMemory
1034570mimiNafta (COI15_nafta)C++17
11 / 100
14 ms10072 KiB
#include <bits/stdc++.h> #define ff first #define ss second #define pp push_back #define all(x) (x).begin(),(x).end() #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define dbg(v) cout << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl; using namespace std; using ll = long long; using ld = long double; using pii = pair <int,int>; using pll = pair <ll,ll>; using pld = pair <ld,ld>; const char el ='\n'; const char sp = ' '; const int maxn = 2e3+5, mod = 1e9+7, N = 10; const ll inf = 1e9L+3; int n,m,id[maxn][maxn],neg[maxn][maxn],sum[maxn],total[maxn],l_[maxn], dp[maxn][maxn], ti,movx[] = {0,0,1,-1}, movy[] = {1,-1,0,0}; char c[maxn][maxn]; map<int,bool> mark; void DFS(int u, int v) { id[u][v] = ti; l_[ti] = min(l_[ti],v); sum[ti]+=c[u][v]-'0'; for(int i=0;i<4;++i) { int x = u+movx[i], y = v+movy[i]; if(x>0 && x<=n && y>0 && y<=m && c[x][y]!='.' && !id[x][y]) DFS(x,y); } } void input() { fill(l_,l_+maxn,inf); cin>>n>>m; for(int i=1;i<=m;++i) dp[m][0] = -inf; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cin>>c[i][j]; for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j){ if(!id[i][j] && c[i][j]!='.'){ ++ti; DFS(i,j); } } } } void prepare() { for(int j=1;j<=m;++j) { mark.clear(); for(int i=1;i<=n;++i) { if(c[i][j]=='.') continue; if(mark[id[i][j]]) continue; mark[id[i][j]] = true; total[j]+=sum[id[i][j]]; neg[l_[id[i][j]]][j]+=sum[id[i][j]]; } for(int i=1;i<=m;++i) neg[i][j]+=neg[i-1][j]; } } int cost(int l, int r) { return total[r]-neg[l][r]; } void cal(int l, int r, int optl, int optr, int j) { if(l>r) return; int mid = (l+r)/2,best = 0; for(int i=optl; i<=min(mid,optr);++i) { int money = dp[i-1][j-1] + cost(i-1,mid); if(money>dp[mid][j]) { dp[mid][j] = money; best = i; } } cal(l,mid-1,optl,best,j); cal(mid+1,r,best,optr,j); } void solve() { for(int i=1;i<=m;++i) { cal(1,m,1,m,i); int ans = 0; for(int j=1;j<=m;++j) ans = max(ans,dp[j][i]); cout<<ans<<el; } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int test = 1; while(test-->0) { input(); prepare(); solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...