oj.uz

Submission #1054848

# Submission time Handle Problem Language Result Execution time Memory
1054848 2024-08-12T12:37:31 Z anonymous321 Nafta (COI15_nafta) C++17
100 / 100
 429 ms 62128 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<pair<int, int>>> pools;
vector<vector<int>> delta;

void calc (vector<int> &dp, vector<int> &new_dp, int l, int r, int optl, int optr) {
    if (l >= r) return;
    if (optl >= optr) abort();
    int mid = (l + r) / 2;
    int opt = -1;
    for (int i = min(mid, optr-1); i >= optl; i--) {
        if (new_dp[mid] < dp[i] + delta[mid][i]) {
            new_dp[mid] = dp[i] + delta[mid][i];
            opt = i;
        }
    }
    if (opt == -1) abort();
    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<pair<int, int>>> (s);
    for (int i = 0; i < s; i++) {
        for (int j = 0; j < R; j++) {
            pools[i].push_back({min_p[pool[j+1][i+1]], pool[j+1][i+1]});
        }
        set<pair<int, int>> s (pools[i].begin(), pools[i].end());
        pools[i] = vector<pair<int, int>>(s.rbegin(), s.rend());
    }
    
    delta = vector<vector<int>> (s+1, vector<int>(s+1, 0));
    for (int i = 1; i < s+1; i++) {
        int id = 0;
        int x = 0;
        for (int j = i; j >= 0; j--) {
            while (id < pools[i-1].size() && pools[i-1][id].first > j) {
                x += oil[pools[i-1][id].second];
                id++;
            }
            delta[i][j] = x;
        }
    }

    vector<int> dp (s+1, 0);
    for (int i = 0; i < s; i++) {
        vector<int> new_dp (s+1, -1);
        calc(dp, new_dp, 1, s+1, 0, s+1);
        cout << *max_element(new_dp.begin(), new_dp.end()) << "\n";
        dp = new_dp;
        dp[0] = 0;
    }
    return 0;
}

Compilation message

nafta.cpp: In function 'int main()':
nafta.cpp:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |             while (id < pools[i-1].size() && pools[i-1][id].first > j) {
      |                    ~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 448 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 344 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 0 ms 344 KB Output is correct
2 Correct 1 ms 448 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 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 7 ms 1752 KB Output is correct
8 Correct 9 ms 1628 KB Output is correct
9 Correct 7 ms 1536 KB Output is correct
10 Correct 8 ms 1908 KB Output is correct
11 Correct 7 ms 1884 KB Output is correct
12 Correct 6 ms 1628 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 448 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 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 7 ms 1752 KB Output is correct
8 Correct 9 ms 1628 KB Output is correct
9 Correct 7 ms 1536 KB Output is correct
10 Correct 8 ms 1908 KB Output is correct
11 Correct 7 ms 1884 KB Output is correct
12 Correct 6 ms 1628 KB Output is correct
13 Correct 357 ms 62128 KB Output is correct
14 Correct 429 ms 59528 KB Output is correct
15 Correct 391 ms 52264 KB Output is correct
16 Correct 305 ms 61472 KB Output is correct
17 Correct 283 ms 59836 KB Output is correct
18 Correct 319 ms 60116 KB Output is correct