oj.uz

답안 #960554

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
960554 2024-04-10T15:49:25 Z Niosakaru Nafta (COI15_nafta) C++17
0 / 100
 7 ms 39772 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] , opt[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];
    rep(i,0,3){
        int x = u + dx[i] , y = v + dy[i];
        if (1 > x || 1 > y || n < x || m < y || vs[x][y] || a[x][y] == -1) continue;
        sum += bfs(x,y);
    }
    return sum;
}

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

    cin >> n >> m;
    memset(a , -1 , sizeof a);
    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] == -1) 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){
            int Le = opt[i][k-1] , Ri = opt[i-1][k]; 
            if (Le > Ri) swap(Le,Ri);
            dp[i][k] = -2e9;
            rep(j,max(0ll,Le-1),min(n,Ri+1)) if (dp[j][k-1] + e[j+1][i] > dp[i][k])
            {
                dp[i][k] = dp[j][k-1] + e[j+1][i];
                opt[i][k] = j;
            }
            rs[k] = max(rs[k] , dp[i][k]);
        }
    }

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

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 39772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 39772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 39772 KB Output isn't correct
2 Halted 0 ms 0 KB -