oj.uz

Submission #980402

# Submission time Handle Problem Language Result Execution time Memory
980402 2024-05-12T07:04:23 Z michified Nafta (COI15_nafta) C++17
34 / 100
 1000 ms 37624 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}};
unordered_map<int, map<int, pii>> intervsCol;
unordered_map<int, 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);
    }
}

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));
    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 (auto& elem : intervsCol) {
        auto itr = elem.second.begin();
        while (itr != elem.second.end()) {
            itr -> second.second = intervsColtot[elem.first];
            intervsColtot[elem.first] += itr -> second.first;
            itr = next(itr);
        }
        elem.second[INT_MAX].second = intervsColtot[elem.first];
    }

    vector<vector<int>> dp(cs + 1, vector<int>(cs));
    for (j = 0; j < cs; j++) dp[1][j] = intervsColtot[j];
    for (i = 2; i <= cs; i++) {
        for (j = 0; j < cs; j++) {
            for (k = i - 1; k <= j; k++) {
                dp[i][j] = max(dp[i][j], dp[i - 1][k - 1] + intervsColtot[j] - intervsCol[j].lower_bound(k) -> second.second);
            }
        }
    }

    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 348 KB Output is correct
2 Correct 1 ms 372 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 348 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 372 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 348 KB Output is correct
7 Correct 60 ms 1372 KB Output is correct
8 Correct 74 ms 1772 KB Output is correct
9 Correct 57 ms 2392 KB Output is correct
10 Correct 61 ms 1372 KB Output is correct
11 Correct 70 ms 1628 KB Output is correct
12 Correct 71 ms 1628 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 372 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 348 KB Output is correct
7 Correct 60 ms 1372 KB Output is correct
8 Correct 74 ms 1772 KB Output is correct
9 Correct 57 ms 2392 KB Output is correct
10 Correct 61 ms 1372 KB Output is correct
11 Correct 70 ms 1628 KB Output is correct
12 Correct 71 ms 1628 KB Output is correct
13 Execution timed out 1031 ms 37624 KB Time limit exceeded
14 Halted 0 ms 0 KB -