Submission #531142

#	Time	Username	Problem	Language	Result	Execution time	Memory
531142		Deepesson	Nafta (COI15_nafta)	C++17	100 / 100	403 ms	23948 KiB

nafta

#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 m = (l+r)/2;
    int best=-1e9,split=0;
    for(int i=la;i<=std::min(m-1,ra);++i){
        int ans = soma[m]-inter[i][m]+prev[i];
        if(ans>best){
            best=ans;
            split=i;
        }
    }
    tab[m]=best;
    DP(l,m-1,la,split);
    DP(m+1,r,split,ra);
}
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]=0;
        }
    }
}

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 66 / 66