oj.uz

Submission #980539

# Submission time Handle Problem Language Result Execution time Memory
980539 2024-05-12T08:26:57 Z michified Nafta (COI15_nafta) C++17
100 / 100
 513 ms 86840 KB 
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
using namespace std;

int rs, cs, lb, rb, tot;
vector<vector<int>> grid, dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}, dp;
vector<map<int, pii>> intervsCol;
vector<int> intervsColtot;
vector<vector<bool>> seen;

void getInterv(int curi, int curj) {
    seen[curi][curj] = true;
    lb = min(lb, curj);
    rb = max(rb, curj);
    tot += grid[curi][curj];
    int nexti, nextj;
    for (auto& dir : dirs) {
        nexti = curi + dir[0];
        nextj = curj + dir[1];
        if (nexti >= 0 and nexti < rs and nextj >= 0 and nextj < cs and not seen[nexti][nextj] and grid[nexti][nextj] != -1) getInterv(nexti, nextj);
    }
}

void solve(int i, int l, int r, int optl, int optr) {
    if (l > r) return;
    int mid = (l + r) / 2, opt = optl, k, cur, best = dp[i - 1][optl - 1] + intervsColtot[mid] - intervsCol[mid].lower_bound(optl) -> second.second;
    for (k = optl; k <= min(mid, optr); k++) {
        cur = dp[i - 1][k - 1] + intervsColtot[mid] - intervsCol[mid].lower_bound(k) -> second.second;
        if (cur > best) {
            best = cur;
            opt = k;
        }
    }
    dp[i][mid] = best;
    solve(i, l, mid - 1, optl, opt);
    solve(i, mid + 1, r, opt, optr);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> rs >> cs;
    grid.resize(rs, vector<int>(cs));
    seen.resize(rs, vector<bool>(cs));
    intervsCol.resize(cs);
    intervsColtot.resize(cs);
    int i, j, k;
    string tmp;
    for (i = 0; i < rs; i++) {
        cin >> tmp;
        for (j = 0; j < cs; j++) {
            if (tmp[j] == '.') grid[i][j] = -1;
            else grid[i][j] = tmp[j] - '0';
        }
    }

    for (i = 0; i < rs; i++) {
        for (j = 0; j < cs; j++) {
            if (not seen[i][j] and grid[i][j] != -1) {
                lb = j;
                rb = j;
                tot = 0;
                getInterv(i, j);
                for (k = lb; k <= rb; k++) intervsCol[k][lb].first += tot;
            }
        }
    }
    for (i = 0; i < cs; i++) {
        auto itr = intervsCol[i].begin();
        while (itr != intervsCol[i].end()) {
            itr -> second.second = intervsColtot[i];
            intervsColtot[i] += itr -> second.first;
            itr = next(itr);
        }
        intervsCol[i][INT_MAX].second = intervsColtot[i];
    }

    dp.resize(cs + 1, vector<int>(cs));
    for (j = 0; j < cs; j++) dp[1][j] = intervsColtot[j];

    for (i = 2; i <= cs; i++) {
        solve(i, i - 1, cs - 1, i - 1, cs - 1);
    }

    for (i = 1; i <= cs; i++) cout << *max_element(dp[i].begin(), dp[i].end()) << endl;
    return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 6 ms 1372 KB Output is correct
8 Correct 8 ms 1460 KB Output is correct
9 Correct 7 ms 2392 KB Output is correct
10 Correct 6 ms 1372 KB Output is correct
11 Correct 7 ms 1372 KB Output is correct
12 Correct 6 ms 1624 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 6 ms 1372 KB Output is correct
8 Correct 8 ms 1460 KB Output is correct
9 Correct 7 ms 2392 KB Output is correct
10 Correct 6 ms 1372 KB Output is correct
11 Correct 7 ms 1372 KB Output is correct
12 Correct 6 ms 1624 KB Output is correct
13 Correct 273 ms 35924 KB Output is correct
14 Correct 426 ms 39860 KB Output is correct
15 Correct 337 ms 86840 KB Output is correct
16 Correct 255 ms 37968 KB Output is correct
17 Correct 513 ms 43308 KB Output is correct
18 Correct 415 ms 42820 KB Output is correct