oj.uz

Submission #552893

# Submission time Handle Problem Language Result Execution time Memory
552893 2022-04-24T09:20:00 Z Jomnoi Nafta (COI15_nafta) C++17
100 / 100
 333 ms 39748 KB 
#include <bits/stdc++.h>
#define DEBUG false
using namespace std;

const int MAX_N = 2e3 + 10;
const int INF = 1e9 + 7;
const int d[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

char table[MAX_N][MAX_N];
int value[MAX_N], intersect[MAX_N][MAX_N];
int dp[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];

void solve(const int &k, const int &l, const int &r, const int &a, const int &b) {
    if(l > r) {
        return;
    }

    int mid = (l + r) / 2, pos;
    dp[k][mid] = -INF;
    for(int i = a; i <= min(mid, b); i++) {
        int res = dp[k - 1][i - 1] + value[mid] - intersect[i - 1][mid];
        if(dp[k][mid] < res) {
            dp[k][mid] = res;
            pos = i;
        }
    }

    solve(k, l, mid - 1, a, pos);
    solve(k, mid + 1, r, pos, b);
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int R, S;
    cin >> R >> S;
    for(int i = 1; i <= R; i++) {
        cin >> (table[i] + 1);
    }

    queue <pair <int, int>> q;
    for(int i = 1; i <= R; i++) {
        for(int j = 1; j <= S; j++) {
            if(visited[i][j] == true or table[i][j] == '.') {
                continue;
            }

            visited[i][j] = true;
            q.emplace(i, j);
            int min_S = S, max_S = 0, sz = 0;
            while(!q.empty()) {
                auto [ux, uy] = q.front();
                q.pop();

                sz += table[ux][uy] - '0';
                min_S = min(min_S, uy);
                max_S = max(max_S, uy);
                for(int i = 0; i < 4; i++) {
                    int vx = ux + d[i][0], vy = uy + d[i][1];
                    if(vx < 1 or vx > R or vy < 1 or vy > S or visited[vx][vy] == true or table[vx][vy] == '.') {
                        continue;
                    }

                    visited[vx][vy] = true;
                    q.emplace(vx, vy);
                }
            }

            for(int s = min_S; s <= max_S; s++) {
                value[s] += sz;
                for(int s2 = s + 1; s2 <= max_S; s2++) {
                    intersect[s][s2] += sz;
                }
            }
        }
    }

    for(int i = 1; i <= S; i++) {
        dp[1][i] = value[i];
    }
    cout << *max_element(dp[1] + 1, dp[1] + S + 1) << '\n';
    for(int i = 2; i <= S; i++) {
        solve(i, i, S, i, S);
        cout << *max_element(dp[i] + 1, dp[i] + S + 1) << '\n';
    }
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 852 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 7 ms 4196 KB Output is correct
8 Correct 9 ms 4220 KB Output is correct
9 Correct 8 ms 4280 KB Output is correct
10 Correct 6 ms 4180 KB Output is correct
11 Correct 7 ms 4180 KB Output is correct
12 Correct 8 ms 4196 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 7 ms 4196 KB Output is correct
8 Correct 9 ms 4220 KB Output is correct
9 Correct 8 ms 4280 KB Output is correct
10 Correct 6 ms 4180 KB Output is correct
11 Correct 7 ms 4180 KB Output is correct
12 Correct 8 ms 4196 KB Output is correct
13 Correct 225 ms 33992 KB Output is correct
14 Correct 252 ms 34176 KB Output is correct
15 Correct 333 ms 39748 KB Output is correct
16 Correct 206 ms 33956 KB Output is correct
17 Correct 293 ms 34468 KB Output is correct
18 Correct 305 ms 34376 KB Output is correct