Submission #900198

#	Time	Username	Problem	Language	Result	Execution time	Memory
900198		Ahmed57	Nafta (COI15_nafta)	C++17	100 / 100	270 ms	120144 KiB

nafta

#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 / 11
• Subtask 2: 23 / 23
• Subtask 3: 66 / 66