oj.uz

Submission #1054617

# Submission time Handle Problem Language Result Execution time Memory
1054617 2024-08-12T11:06:45 Z anonymous321 Nafta (COI15_nafta) C++17
34 / 100
 1000 ms 40108 KB 
#include <bits/stdc++.h>
using namespace std;
typedef vector<vector<bool>> vvb;
const int INF = numeric_limits<int>::max()/2;

int R;
vector<int> oil {0};
vector<int> min_p {0};
vector<vector<int>> pool;
vector<vector<int>> pools;

void calc (vector<int> &dp, vector<int> &new_dp, int l, int r, int optl, int optr) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    int opt = -1;
    for (int i = optl; i < optr; i++) {
        if (i >= mid) break;
        int x = dp[i];
        for (auto &it: pools[mid-1]) {
            if (min_p[it] > i) {
                x += oil[it];
            }
        }
        if (new_dp[mid] < x) {
            new_dp[mid] = x;
            opt = i;
        }
    }
    calc(dp, new_dp, l, mid, optl, opt+1);
    calc(dp, new_dp, mid+1, r, opt, optr);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int r, s;
    cin >> r >> s;
    R = r;
    vector<vector<int>> m (r+2, vector<int>(s+2, -1));
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < s; j++) {
            char c;
            cin >> c;
            if (c != '.') {
                m[i+1][j+1] = c - '0';
            }
        }
    }
    
    int cnt = 1;
    pool = vector<vector<int>>(r+2, vector<int>(s+2, 0));
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < s; j++) {
            if (m[i+1][j+1] != -1 && pool[i+1][j+1] == 0) {
                int cur = cnt++;
                pool[i+1][j+1] = cur;
                oil.push_back(0);
                min_p.push_back(j+1);
                queue<pair<int, int>> q {};
                q.push({i+1, j+1});
                while (!q.empty()) {
                    auto[x, y] = q.front();
                    q.pop();
                    oil[cur] += m[x][y];
                    min_p[cur] = min(min_p[cur], y);
                    vector<pair<int, int>> nb {{x, y-1}, {x, y+1}, {x-1, y}, {x+1, y}};
                    for (auto[itx, ity] : nb) {
                        if (m[itx][ity] != -1 && pool[itx][ity] == 0) {
                            pool[itx][ity] = cur;
                            q.push({itx, ity});
                        }
                    }
                }
            }
        }
    }

    pools = vector<vector<int>> (s);
    for (int i = 0; i < s; i++) {
        vector<bool> t (cnt, false);
        for (int j = 0; j < R; j++) {
            if (!t[pool[j+1][i+1]]) {
                t[pool[j+1][i+1]] = true;
                pools[i].push_back(pool[j+1][i+1]);
            }
        }
    }
    

    vector<int> dp (s+1, 0);
    vector<int> new_dp = dp;
    for (int i = 0; i < s; i++) {
        calc(dp, new_dp, 1, s+1, 0, s+1);
        cout << *max_element(new_dp.begin(), new_dp.end()) << "\n";
        swap(dp, new_dp);
        new_dp.assign(s+1, -1);
    }
    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 0 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 0 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 0 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 0 ms 348 KB Output is correct
7 Correct 53 ms 1392 KB Output is correct
8 Correct 66 ms 1332 KB Output is correct
9 Correct 8 ms 1112 KB Output is correct
10 Correct 67 ms 1340 KB Output is correct
11 Correct 100 ms 1368 KB Output is correct
12 Correct 70 ms 1116 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 0 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 0 ms 348 KB Output is correct
7 Correct 53 ms 1392 KB Output is correct
8 Correct 66 ms 1332 KB Output is correct
9 Correct 8 ms 1112 KB Output is correct
10 Correct 67 ms 1340 KB Output is correct
11 Correct 100 ms 1368 KB Output is correct
12 Correct 70 ms 1116 KB Output is correct
13 Execution timed out 1086 ms 40108 KB Time limit exceeded
14 Halted 0 ms 0 KB -