oj.uz

Submission #531141

# Submission time Handle Problem Language Result Execution time Memory
531141 2022-02-27T20:00:07 Z Deepesson Nafta (COI15_nafta) C++17
100 / 100
 390 ms 27912 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){
        ///Todos os segmentos de M - compartilhados de [i][M] + dp de i
        int ans = soma[m]-inter[i][m]+prev[i];
        if(ans>best){
            best=ans;
            split=i;
        }
    }
    //std::cout<<"Split "<<m<<" "<<split<<"\n";
    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});
            }
            ///std::cout<<"Seg "<<left<<" "<<right<<" "<<total<<"\n";
            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<<prev[i]<<" ";
    }
   // std::cout<<"\n";
    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){
        //    std::cout<<tab[j]<<" ";
            prev[j]=tab[j];
            tab[j]=0;
        }
       // std::cout<<"\n";
    }
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 708 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 708 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 3148 KB Output is correct
8 Correct 8 ms 3064 KB Output is correct
9 Correct 9 ms 3148 KB Output is correct
10 Correct 7 ms 3172 KB Output is correct
11 Correct 6 ms 3148 KB Output is correct
12 Correct 5 ms 3152 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 708 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 3148 KB Output is correct
8 Correct 8 ms 3064 KB Output is correct
9 Correct 9 ms 3148 KB Output is correct
10 Correct 7 ms 3172 KB Output is correct
11 Correct 6 ms 3148 KB Output is correct
12 Correct 5 ms 3152 KB Output is correct
13 Correct 299 ms 27800 KB Output is correct
14 Correct 371 ms 27736 KB Output is correct
15 Correct 390 ms 27860 KB Output is correct
16 Correct 262 ms 27800 KB Output is correct
17 Correct 277 ms 27912 KB Output is correct
18 Correct 266 ms 27808 KB Output is correct