oj.uz

Submission #521176

# Submission time Handle Problem Language Result Execution time Memory
521176 2022-02-01T07:11:24 Z pokmui9909 Nafta (COI15_nafta) C++17
100 / 100
 482 ms 133724 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1192 KB Output is correct
2 Correct 1 ms 1228 KB Output is correct
3 Correct 1 ms 1300 KB Output is correct
4 Correct 1 ms 1092 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1192 KB Output is correct
2 Correct 1 ms 1228 KB Output is correct
3 Correct 1 ms 1300 KB Output is correct
4 Correct 1 ms 1092 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct
7 Correct 13 ms 8656 KB Output is correct
8 Correct 15 ms 8516 KB Output is correct
9 Correct 11 ms 8604 KB Output is correct
10 Correct 11 ms 7648 KB Output is correct
11 Correct 9 ms 7628 KB Output is correct
12 Correct 8 ms 7624 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1192 KB Output is correct
2 Correct 1 ms 1228 KB Output is correct
3 Correct 1 ms 1300 KB Output is correct
4 Correct 1 ms 1092 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct
7 Correct 13 ms 8656 KB Output is correct
8 Correct 15 ms 8516 KB Output is correct
9 Correct 11 ms 8604 KB Output is correct
10 Correct 11 ms 7648 KB Output is correct
11 Correct 9 ms 7628 KB Output is correct
12 Correct 8 ms 7624 KB Output is correct
13 Correct 370 ms 133696 KB Output is correct
14 Correct 410 ms 133724 KB Output is correct
15 Correct 482 ms 133652 KB Output is correct
16 Correct 337 ms 121964 KB Output is correct
17 Correct 354 ms 121960 KB Output is correct
18 Correct 351 ms 121964 KB Output is correct