oj.uz

Submission #1103478

# Submission time Handle Problem Language Result Execution time Memory
1103478 2024-10-21T03:57:05 Z doducanh Nafta (COI15_nafta) C++14
100 / 100
 224 ms 106920 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=rl;i<=min(m-1,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[maxx][k]+=tmp;
            }
        }
    }
    for(int i=0;i<=m+1;i++){
        for(int j=0;j<=m+1;j++){
            w[i][j]=0;
            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+1,0,m+1);
        for(int j=0;j<=m+1;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 8784 KB Output is correct
2 Correct 2 ms 8784 KB Output is correct
3 Correct 2 ms 8784 KB Output is correct
4 Correct 2 ms 8788 KB Output is correct
5 Correct 2 ms 8788 KB Output is correct
6 Correct 2 ms 8788 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8784 KB Output is correct
2 Correct 2 ms 8784 KB Output is correct
3 Correct 2 ms 8784 KB Output is correct
4 Correct 2 ms 8788 KB Output is correct
5 Correct 2 ms 8788 KB Output is correct
6 Correct 2 ms 8788 KB Output is correct
7 Correct 6 ms 19796 KB Output is correct
8 Correct 8 ms 19796 KB Output is correct
9 Correct 11 ms 19796 KB Output is correct
10 Correct 6 ms 19796 KB Output is correct
11 Correct 6 ms 19796 KB Output is correct
12 Correct 6 ms 19852 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8784 KB Output is correct
2 Correct 2 ms 8784 KB Output is correct
3 Correct 2 ms 8784 KB Output is correct
4 Correct 2 ms 8788 KB Output is correct
5 Correct 2 ms 8788 KB Output is correct
6 Correct 2 ms 8788 KB Output is correct
7 Correct 6 ms 19796 KB Output is correct
8 Correct 8 ms 19796 KB Output is correct
9 Correct 11 ms 19796 KB Output is correct
10 Correct 6 ms 19796 KB Output is correct
11 Correct 6 ms 19796 KB Output is correct
12 Correct 6 ms 19852 KB Output is correct
13 Correct 150 ms 106828 KB Output is correct
14 Correct 180 ms 106920 KB Output is correct
15 Correct 224 ms 106892 KB Output is correct
16 Correct 112 ms 106800 KB Output is correct
17 Correct 130 ms 106836 KB Output is correct
18 Correct 121 ms 106728 KB Output is correct