oj.uz

Submission #1054505

# Submission time Handle Problem Language Result Execution time Memory
1054505 2024-08-12T10:19:50 Z anonymous321 Nafta (COI15_nafta) C++17
34 / 100
 1000 ms 289408 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;

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) continue;
        int x = dp[i];
        vector<bool> t = dp_t[i];
        for (int j = 0; j < R; j++) {
            if (!t[pool[j+1][mid]]) {
                x += oil[pool[j+1][mid]];
                t[pool[j+1][mid]] = 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});
                        }
                    }
                }
            }
        }
    }

    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 6 ms 344 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 5 ms 496 KB Output is correct
6 Correct 2 ms 348 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 5 ms 496 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 508 ms 2208 KB Output is correct
8 Correct 346 ms 1800 KB Output is correct
9 Correct 211 ms 1344 KB Output is correct
10 Correct 381 ms 1900 KB Output is correct
11 Correct 527 ms 1456 KB Output is correct
12 Correct 409 ms 1372 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 5 ms 496 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 508 ms 2208 KB Output is correct
8 Correct 346 ms 1800 KB Output is correct
9 Correct 211 ms 1344 KB Output is correct
10 Correct 381 ms 1900 KB Output is correct
11 Correct 527 ms 1456 KB Output is correct
12 Correct 409 ms 1372 KB Output is correct
13 Execution timed out 1087 ms 289408 KB Time limit exceeded
14 Halted 0 ms 0 KB -