oj.uz

Submission #1103481

# Submission time Handle Problem Language Result Execution time Memory
1103481 2024-10-21T04:03:21 Z doducanh Nafta (COI15_nafta) C++14
100 / 100
 192 ms 102936 KB 
///breaker
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define fi first
#define se second
#define ii pair<int,int>
#define mp make_pair
#define in(x) freopen(x,"r",stdin)
#define out(x) freopen(x,"w",stdout)
#define bit(x,i) ((x>>i)&1)
#define lc (id<<1)
#define rc ((id<<1)^1)
const int maxn=2e3+7;
const int inf=1e9+7;
int dx[4]={1,0,0,-1};
int dy[4]={0,-1,1,0};
string s[maxn];
int val[maxn];
bool vst[maxn][maxn];
int w[maxn][maxn];
int I[maxn][maxn];
int dp[maxn][maxn];
int n,m;
bool check(int x,int y)
{
    return (1<=x&&x<=n&&1<=y&&y<=m&&vst[x][y]==0&&s[x][y]>='0'&&s[x][y]<='9');
}
void dvc(int lvl,int l,int r,int rl,int rr)
{
    if(l>r)return;
    int m=(l+r)/2;
    int best=-inf,pos;
    for(int i=max(rl,m+1);i<=rr;i++){
        int tmp=dp[lvl-1][i]+w[m][i];
        if(tmp>best){
            best=tmp;
            pos=i;
        }
    }
    dp[lvl][m]=best;
    dvc(lvl,l,m-1,rl,pos);
    dvc(lvl,m+1,r,pos,rr);
}
void sol(void){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        s[i]=" "+s[i];
    }
    for(int i=1;i<=m;i++){
        for(int j=0;j<=m;j++){
            dp[i][j]=-inf;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!check(i,j))continue;
            queue<ii>q;
            q.push({i,j});
            int minn=j;
            int maxx=j;
            int tmp=0;
            vst[i][j]=1;
            while(q.size()){
                int x=q.front().fi;
                int y=q.front().se;
                tmp+=(s[x][y]-'0');
                minn=min(minn,y);
                maxx=max(maxx,y);
                q.pop();
                for(int k=0;k<4;k++){
                    int nx=x+dx[k];
                    int ny=y+dy[k];
                    if(!check(nx,ny))continue;
                    q.push({nx,ny});
                    vst[nx][ny]=1;
                }
            }
            for(int k=minn;k<=maxx;k++){
                I[minn][k]+=tmp;
            }
        }
    }
    for(int i=m;i>=0;i--){
        for(int j=1;j<=m;j++){
            w[i][j]=w[i+1][j]+I[i+1][j];
        }
    }
    dp[0][0]=0;
    int res=0;
    for(int i=1;i<=m;i++){
        dvc(i,0,m,0,m);
        
        for(int j=0;j<=m;j++){
            res=max(res,dp[i][j]);
        }
        cout<<res<<"\n";
    }
 
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    while(t--){
        sol();
    }
    // you should actually read the stuff at the bottom
    return 0;
}
/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

Compilation message

nafta.cpp: In function 'void dvc(long long int, long long int, long long int, long long int, long long int)':
nafta.cpp:44:8: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   44 |     dvc(lvl,l,m-1,rl,pos);
      |     ~~~^~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6736 KB Output is correct
2 Correct 1 ms 6736 KB Output is correct
3 Correct 1 ms 6736 KB Output is correct
4 Correct 1 ms 6736 KB Output is correct
5 Correct 1 ms 6736 KB Output is correct
6 Correct 1 ms 6736 KB Output is correct
7 Correct 6 ms 18256 KB Output is correct
8 Correct 7 ms 18428 KB Output is correct
9 Correct 7 ms 18512 KB Output is correct
10 Correct 5 ms 18256 KB Output is correct
11 Correct 5 ms 18256 KB Output is correct
12 Correct 5 ms 18256 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6736 KB Output is correct
2 Correct 1 ms 6736 KB Output is correct
3 Correct 1 ms 6736 KB Output is correct
4 Correct 1 ms 6736 KB Output is correct
5 Correct 1 ms 6736 KB Output is correct
6 Correct 1 ms 6736 KB Output is correct
7 Correct 6 ms 18256 KB Output is correct
8 Correct 7 ms 18428 KB Output is correct
9 Correct 7 ms 18512 KB Output is correct
10 Correct 5 ms 18256 KB Output is correct
11 Correct 5 ms 18256 KB Output is correct
12 Correct 5 ms 18256 KB Output is correct
13 Correct 136 ms 102728 KB Output is correct
14 Correct 169 ms 102936 KB Output is correct
15 Correct 192 ms 102728 KB Output is correct
16 Correct 131 ms 102716 KB Output is correct
17 Correct 124 ms 102800 KB Output is correct
18 Correct 103 ms 102728 KB Output is correct