oj.uz

Submission #1099637

# Submission time Handle Problem Language Result Execution time Memory
1099637 2024-10-11T21:36:47 Z Thunnus Nafta (COI15_nafta) C++17
100 / 100
 397 ms 27892 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 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;
        }
    }
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4560 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 5 ms 7260 KB Output is correct
8 Correct 6 ms 7260 KB Output is correct
9 Correct 7 ms 7260 KB Output is correct
10 Correct 4 ms 7260 KB Output is correct
11 Correct 4 ms 7260 KB Output is correct
12 Correct 6 ms 7384 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4560 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 5 ms 7260 KB Output is correct
8 Correct 6 ms 7260 KB Output is correct
9 Correct 7 ms 7260 KB Output is correct
10 Correct 4 ms 7260 KB Output is correct
11 Correct 4 ms 7260 KB Output is correct
12 Correct 6 ms 7384 KB Output is correct
13 Correct 190 ms 27800 KB Output is correct
14 Correct 325 ms 27732 KB Output is correct
15 Correct 276 ms 27848 KB Output is correct
16 Correct 161 ms 27732 KB Output is correct
17 Correct 295 ms 27728 KB Output is correct
18 Correct 397 ms 27892 KB Output is correct