Submission #1099637

#TimeUsernameProblemLanguageResultExecution timeMemory
1099637ThunnusNafta (COI15_nafta)C++17
100 / 100
397 ms27892 KiB
#include <bits/stdc++.h> #define MAX 2005 char ch[MAX][MAX]; typedef std::pair<int,int> pii; bool visitou[MAX][MAX]; int inter[MAX][MAX]; int soma[MAX]; int prev[MAX]; int tab[MAX]; void DP(int l,int r,int la,int ra){ if(l > r) return; int mid = (l + r) / 2, lst = 0; for(int i = la; i <= std::min(mid - 1, r); i++){ int cost = prev[i] + soma[mid] - inter[i][mid]; if(cost > tab[mid]){ tab[mid] = cost; lst = i; } } DP(l, mid - 1, la, lst); DP(mid + 1, r, lst, ra); return; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int N,M; std::cin>>N>>M; for(int i=0;i!=N;++i){ for(int j=0;j!=M;++j){ std::cin>>ch[i][j]; } } for(int i=0;i!=N;++i){ for(int j=0;j!=M;++j){ if(ch[i][j]=='.'||visitou[i][j])continue; std::queue<pii> queue; queue.push({i,j}); long long total=0; int left=j,right=j; while(queue.size()){ auto __ = queue.front(); queue.pop(); if(__.first<0||__.second<0)continue; if(__.first>=N||__.second>=M)continue; if(ch[__.first][__.second]=='.')continue; if(visitou[__.first][__.second])continue; visitou[__.first][__.second]=1; total+=ch[__.first][__.second]-'0'; left=std::min(left,__.second); right=std::max(right,__.second); queue.push({__.first+1,__.second}); queue.push({__.first-1,__.second}); queue.push({__.first,__.second+1}); queue.push({__.first,__.second-1}); } soma[left]+=total; soma[right+1]-=total; for(int k=left;k!=right+1;++k){ inter[k][left]+=total; inter[k][right+1]-=total; } } } { int s=0; for(int i=0;i!=M;++i){ s+=soma[i]; soma[i]=s; } for(int i=0;i!=M;++i){ int s=0; for(int j=0;j!=M;++j){ s+=inter[i][j]; inter[i][j]=s; } } } int resp1=0; for(int i=0;i!=M;++i){ prev[i]=soma[i]; resp1=std::max(resp1,soma[i]); } std::cout<<resp1<<"\n"; for(int i=1;i!=M;++i){ DP(i,M-1,0,M-1); std::cout<<*std::max_element(tab,&tab[M])<<"\n"; for(int j=0;j!=M;++j){ prev[j]=tab[j]; tab[j] = INT32_MIN; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...