oj.uz

Submission #1054543

# Submission time Handle Problem Language Result Execution time Memory
1054543 2024-08-12T10:34:44 Z anonymous321 Nafta (COI15_nafta) C++17
34 / 100
 1000 ms 291688 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<vector<int>> pool;
vector<vector<int>> pools;

void calc (vector<int> &dp, vvb &dp_t, vector<int> &new_dp, vvb &new_dp_t, 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];
        vector<bool> t = dp_t[i];
        for (auto &it: pools[mid-1]) {
            if (!t[it]) {
                x += oil[it];
                t[it] = true;
            }
        }
        if (new_dp[mid] < x) {
            new_dp[mid] = x;
            new_dp_t[mid] = t;
            opt = i;
        }
    }
    calc(dp, dp_t, new_dp, new_dp_t, l, mid, optl, opt+1);
    calc(dp, dp_t, new_dp, new_dp_t, 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);
                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];
                    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<vector<bool>> dp_t (s+1, vector<bool>(cnt, false));
    vector<int> new_dp = dp;
    vector<vector<bool>> new_dp_t = dp_t;
    for (int i = 0; i < s; i++) {
        //vector<int> new_dp (s+1, -1);
        //vector<vector<bool>> new_dp_t (s+1, vector<bool>(cnt, false));
        calc(dp, dp_t, new_dp, new_dp_t, 1, s+1, 0, s+1);
        cout << *max_element(new_dp.begin(), new_dp.end()) << "\n";
        swap(dp, new_dp);
        swap(dp_t, new_dp_t);
        new_dp.assign(s+1, -1);
    }
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 3 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 4 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 4 ms 348 KB Output is correct
2 Correct 3 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 4 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 215 ms 2264 KB Output is correct
8 Correct 106 ms 1884 KB Output is correct
9 Correct 24 ms 1392 KB Output is correct
10 Correct 133 ms 1936 KB Output is correct
11 Correct 274 ms 1608 KB Output is correct
12 Correct 227 ms 1372 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 3 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 4 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 215 ms 2264 KB Output is correct
8 Correct 106 ms 1884 KB Output is correct
9 Correct 24 ms 1392 KB Output is correct
10 Correct 133 ms 1936 KB Output is correct
11 Correct 274 ms 1608 KB Output is correct
12 Correct 227 ms 1372 KB Output is correct
13 Execution timed out 1044 ms 291688 KB Time limit exceeded
14 Halted 0 ms 0 KB -