oj.uz

Submission #900198

# Submission time Handle Problem Language Result Execution time Memory
900198 2024-01-07T21:02:01 Z Ahmed57 Nafta (COI15_nafta) C++17
100 / 100
 270 ms 120144 KB 
#include <bits/stdc++.h>

using namespace std;
#define int long long
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int n,m , ma , mi , lol = 0;
char arr[2002][2002];
bool vis[2002][2002];
int dp[2002][2002];
int cost[2002][2002];
int level = 1;
void dc(int l,int r,int optl,int optr){
    //cout<<"ggg"<<endl;
    if(l>r)return ;
    int mid = (l+r)/2;
    pair<int,int> p = {-1e18,-1e18};
    int sum = 0;
    //cout<<level<<" "<<l<<" "<<r<<" "<<optl<<endl;
    for(int i = min(optr,mid-1);i>=max(optl,0ll);i--){
        sum=(cost[mid][m]-cost[mid][mid-1])-(cost[i][m]-cost[i][mid-1]);
        p = max(p,make_pair(dp[level-1][i]+sum,i));
    }
    //cout<<"ff"<<endl;
    dp[level][mid] = p.first;
    int opt = p.second;
    dc(l,mid-1,optl,opt);
    dc(mid+1,r,opt,optr);
}
void dfs(int i,int j){
    lol+=arr[i][j]-'0';
    ma = max(ma,j);
    mi = min(mi,j);
    vis[i][j] = 1;
    for(int e = 0;e<4;e++){
        int nx = i+dx[e];
        int ny = j+dy[e];
        if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&arr[nx][ny]!='.'&&!vis[nx][ny]){
            dfs(nx,ny);
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("outout.txt","w",stdout);
    cin>>n>>m;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            cin>>arr[i][j];
        }
    }
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            if(!vis[i][j]&&arr[i][j]!='.'){
                ma = 0 , mi = 1e9;
                lol = 0;dfs(i,j);
                cost[mi][ma]+=lol;
            }
        }
    }
    for(int i = 1;i<=m;i++){
        for(int j = 1;j<=m;j++){
            cost[i][j]+=cost[i][j-1];
        }
    }
    for(int i = 1;i<=m;i++){
        for(int j = 1;j<=m;j++){
            cost[i][j]+=cost[i-1][j];
        }
    }
    for(int i = 0;i<=m;i++){
        for(int j = 0;j<=m;j++)dp[i][j] = -1e18;
    }
    dp[0][0] = 0;
    level = 1;
    while(level<=m){
        //cout<<level<<endl;
        dc(1,m,0,m-1);
        int ma = 0;
        for(int i = 1;i<=m;i++){
            ma = max(ma,dp[level][i]);
        }
        cout<<ma<<"\n";
        level++;
    }
    //cout<<"hhh"<<endl;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6780 KB Output is correct
7 Correct 6 ms 15452 KB Output is correct
8 Correct 7 ms 15452 KB Output is correct
9 Correct 8 ms 16476 KB Output is correct
10 Correct 5 ms 15452 KB Output is correct
11 Correct 5 ms 15448 KB Output is correct
12 Correct 5 ms 15448 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6780 KB Output is correct
7 Correct 6 ms 15452 KB Output is correct
8 Correct 7 ms 15452 KB Output is correct
9 Correct 8 ms 16476 KB Output is correct
10 Correct 5 ms 15452 KB Output is correct
11 Correct 5 ms 15448 KB Output is correct
12 Correct 5 ms 15448 KB Output is correct
13 Correct 188 ms 75092 KB Output is correct
14 Correct 225 ms 74836 KB Output is correct
15 Correct 270 ms 120144 KB Output is correct
16 Correct 166 ms 74832 KB Output is correct
17 Correct 154 ms 74836 KB Output is correct
18 Correct 152 ms 74836 KB Output is correct