oj.uz

Submission #900195

# Submission time Handle Problem Language Result Execution time Memory
900195 2024-01-07T21:00:08 Z Ahmed57 Nafta (COI15_nafta) C++17
0 / 100
 2 ms 2396 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[2001][2001];
bool vis[2001][2001];
int dp[2001][2001];
int cost[2001][2001];
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;
}

Compilation message

nafta.cpp: In function 'int main()':
nafta.cpp:45:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     freopen("input.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
nafta.cpp:46:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     freopen("outout.txt","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -