oj.uz

Submission #531142

# Submission time Handle Problem Language Result Execution time Memory
531142 2022-02-27T20:00:54 Z Deepesson Nafta (COI15_nafta) C++17
100 / 100
 403 ms 23948 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 716 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 7 ms 3052 KB Output is correct
8 Correct 7 ms 3084 KB Output is correct
9 Correct 8 ms 3020 KB Output is correct
10 Correct 5 ms 3020 KB Output is correct
11 Correct 6 ms 3020 KB Output is correct
12 Correct 5 ms 3020 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 7 ms 3052 KB Output is correct
8 Correct 7 ms 3084 KB Output is correct
9 Correct 8 ms 3020 KB Output is correct
10 Correct 5 ms 3020 KB Output is correct
11 Correct 6 ms 3020 KB Output is correct
12 Correct 5 ms 3020 KB Output is correct
13 Correct 317 ms 23880 KB Output is correct
14 Correct 366 ms 23896 KB Output is correct
15 Correct 403 ms 23948 KB Output is correct
16 Correct 255 ms 23788 KB Output is correct
17 Correct 260 ms 23808 KB Output is correct
18 Correct 257 ms 23896 KB Output is correct