Submission #521176

#	Time	Username	Problem	Language	Result	Execution time	Memory
521176		pokmui9909	Nafta (COI15_nafta)	C++17	100 / 100	482 ms	133724 KiB

nafta

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll xdir[4] = {-1, 1, 0, 0};
ll ydir[4] = {0, 0, -1, 1};
ll N, M;
char A[2005][2005];
ll visited[2005][2005];
ll C[2005][2005];
ll D[2005][2005];
ll opt[2005][2005];
ll f(ll x, ll y){
    return C[y][y] - C[x][y];
}

void dnc(ll n, ll s, ll e, ll l, ll r){
    if(s > e) return;
    ll m = (s + e) / 2;
    D[n][m] = -1e18;
    for(int i = l; i <= min(m - 1, r); i++){
        ll v = D[n - 1][i] + f(i, m);
        if(D[n][m] < v){
            D[n][m] = v;
            opt[n][m] = i;
        }
    }
    dnc(n, s, m - 1, l, opt[n][m]);
    dnc(n, m + 1, e, opt[n][m], r);
}

int main(){
    cin.tie(0) -> sync_with_stdio(false);

    cin >> N >> M;
    for(int i = 0; i < N; i++){
        cin >> A[i];
    }
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            if(visited[i][j]) continue;
            if(A[i][j] == '.') continue;
            queue<pair<ll, ll>> Q;
            Q.push({i, j});
            ll L = j, R = j, V = 0;
            V += A[i][j] - '0';
            visited[i][j] = 1;
            while(!Q.empty()){
                ll x = Q.front().first, y = Q.front().second;
                Q.pop();
                for(int k = 0; k < 4; k++){
                    ll nx = x + xdir[k], ny = y + ydir[k];
                    if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                    if(visited[nx][ny]) continue;
                    if(A[nx][ny] == '.') continue;
                    visited[nx][ny] = 1;
                    Q.push({nx, ny});
                    L = min(L, ny);
                    R = max(R, ny);
                    V += A[nx][ny] - '0';
                }
            }
            L++; R++;
            C[L][L] += V;
            C[R + 1][R + 1] += V;
            C[L][R + 1] -= V;
            C[R + 1][L] -= V;
        }
    }
    for(int i = 1; i <= M; i++){
        for(int j = 1; j <= M; j++){
            C[i][j] += C[i - 1][j] + C[i][j - 1];
            C[i][j] -= C[i - 1][j - 1];
        }
    }
    for(int i = 1; i <= M; i++){
        dnc(i, 1, M, 0, M - 1);
        cout << *max_element(D[i], D[i] + M + 1) << '\n';
    }
}

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 66 / 66