oj.uz

Submission #1054536

# Submission time Handle Problem Language Result Execution time Memory
1054536 2024-08-12T10:31:50 Z anonymous321 Nafta (COI15_nafta) C++17
34 / 100
 1000 ms 291868 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";
        dp = new_dp;
        dp_t = new_dp_t;
    }
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 4 ms 348 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 5 ms 344 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 269 ms 2340 KB Output is correct
8 Correct 119 ms 1888 KB Output is correct
9 Correct 26 ms 1368 KB Output is correct
10 Correct 153 ms 2064 KB Output is correct
11 Correct 293 ms 1628 KB Output is correct
12 Correct 254 ms 1368 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 269 ms 2340 KB Output is correct
8 Correct 119 ms 1888 KB Output is correct
9 Correct 26 ms 1368 KB Output is correct
10 Correct 153 ms 2064 KB Output is correct
11 Correct 293 ms 1628 KB Output is correct
12 Correct 254 ms 1368 KB Output is correct
13 Execution timed out 1054 ms 291868 KB Time limit exceeded
14 Halted 0 ms 0 KB -