oj.uz

Submission #980424

# Submission time Handle Problem Language Result Execution time Memory
980424 2024-05-12T07:16:46 Z michified Nafta (COI15_nafta) C++17
34 / 100
 1000 ms 33492 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);
    }
}



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++) {
        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 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 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 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 16 ms 1116 KB Output is correct
8 Correct 22 ms 1372 KB Output is correct
9 Correct 14 ms 2396 KB Output is correct
10 Correct 15 ms 1116 KB Output is correct
11 Correct 21 ms 1512 KB Output is correct
12 Correct 22 ms 1368 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 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 16 ms 1116 KB Output is correct
8 Correct 22 ms 1372 KB Output is correct
9 Correct 14 ms 2396 KB Output is correct
10 Correct 15 ms 1116 KB Output is correct
11 Correct 21 ms 1512 KB Output is correct
12 Correct 22 ms 1368 KB Output is correct
13 Execution timed out 1030 ms 33492 KB Time limit exceeded
14 Halted 0 ms 0 KB -