Submission #1034598

#TimeUsernameProblemLanguageResultExecution timeMemory
1034598mimiNafta (COI15_nafta)C++17
100 / 100
369 ms177688 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define ff first #define ss second #define pp push_back #define all(x) (x).begin(),(x).end() #define dbg(v) cout << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl; using namespace std; using ll = long long; using ld = long double; using pii = pair <ll,ll>; using pll = pair <ll,ll>; using pld = pair <ld,ld>; const char el ='\n'; const char sp = ' '; const ll maxn = 3e3+5, mod = 1e9+7, maxN = 1e6; const ll inf = 1e18L+3; ll 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<ll,bool> mark; void DFS(ll u, ll v) { id[u][v] = ti; l_[ti] = min(l_[ti],v); sum[ti]+=c[u][v]-'0'; for(ll i=0;i<4;++i) { ll 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(ll i=1;i<=m;++i) dp[m][0] = -inf; for(ll i=1;i<=n;++i) for(ll j=1;j<=m;++j) cin>>c[i][j]; for(ll i=1;i<=n;++i){ for(ll j=1;j<=m;++j){ if(!id[i][j] && c[i][j]!='.'){ ++ti; DFS(i,j); } } } } void prepare() { for(ll j=1;j<=m;++j) { mark.clear(); for(ll 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(ll i=1;i<=m;++i) neg[i][j]+=neg[i-1][j]; } } ll cost(ll l, ll r) { return total[r]-neg[l][r]; } void cal(ll l, ll r, ll optl, ll optr, ll j) { if(l>r) return; ll mid = (l+r)/2,best = 0; for(ll i=optl; i<=min(mid,optr);++i) { ll 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(ll i=1;i<=m;++i) { cal(1,m,1,m,i); ll ans = 0; for(ll 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); ll 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...