oj.uz

Submission #960531

# Submission time Handle Problem Language Result Execution time Memory
960531 2024-04-10T15:26:45 Z Niosakaru Nafta (COI15_nafta) C++17
0 / 100
 2 ms 7004 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i,l,r) for (int i = l ; i <= r ; i ++)
#define N 2020

const int mod = 1e9 + 7 , base = 311;

int n , m , s , r , w[N][N] , e[N][N] , a[N][N] , vs[N][N] , rs[N] , dp[N][N] , dx[] = {0,0,-1,1} , dy[] = {1,-1,0,0};

int bfs(int u,int v){
    r = max(r,v); vs[u][v] = 1;
    int sum = a[u][v] , x , y;
    rep(i,0,3){
        x = u + dx[i] , y = v + dy[i];
        if (1 > x || 1 > y || n < x || m < y || vs[x][y] || !a[x][y]) continue;
        sum += bfs(x,y);
    }
    return sum;
}

signed main(){
    cin.tie(NULL)->sync_with_stdio(NULL);

    cin >> n >> m;
    rep(i,1,n) rep(j,1,m)
    {
        char c; cin >> c;
        if (c == '.') continue;
        a[i][j] = c - '0';
    }

    rep(j,1,m) rep(i,1,n)
    {
        if (vs[i][j] || !a[i][j]) continue;
        r = j , s = bfs(i,j);
        w[j][r] += s;
    }

    for (int i = m ; i ; i --){
        s = 0;
        for (int j = m ; j >= i ; j --){
            s += w[i][j];
            e[i][j] = e[i + 1][j] + s;
        }
    }

    rep(k,1,m){
        rep(i,1,m) rep(j,0,i-1){
            dp[i][k] = max(dp[i][k] , dp[j][k - 1] + e[j + 1][i]);
            rs[k] = max(rs[k] , dp[i][k]);
        }
    }

    rep(i,1,m)
        cout << rs[i] << '\n';
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 7004 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 7004 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 7004 KB Output isn't correct
2 Halted 0 ms 0 KB -