oj.uz

Submission #989049

# Submission time Handle Problem Language Result Execution time Memory
989049 2024-05-27T11:04:13 Z vjudge1 Nafta (COI15_nafta) C++17
100 / 100
 277 ms 118344 KB 
#include "bits/stdc++.h"
using namespace std;
struct range {
    struct itr2 {
        int i;
        constexpr itr2(const int &i) noexcept: i(i) {}
    };
    struct itr1 {
        int i, step;
        constexpr itr1(const int &i, const int &step)
            noexcept: i(i), step(step) { assert(step); }
        void operator ++ () noexcept { i += step; }
        constexpr int operator * () const noexcept { return i; }
        constexpr bool operator != (const itr2 &x) const noexcept {
            return step > 0 ? i <= x.i : i >= x.i;
        }
    };
    const itr1 start;
    const itr2 stop;
    constexpr range(const int &stop)
        noexcept: start(1, 1), stop(stop) {}
    constexpr range(const int &start, const int &stop)
        noexcept: start(start, 1), stop(stop) {}
    constexpr range(const int &start, const int &stop, const int &step)
        noexcept: start(start, step), stop(stop) {}
    constexpr itr1 begin() const noexcept { return start; }
    constexpr itr2 end() const noexcept { return stop; }
};
bool START;
void init();
void Nguyen_Tuong_Duy();
bool multitest();
void time_and_memory();
clock_t TIME = clock();
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(ios::badbit | ios::failbit);
    init();
    int TEST = 1;
    if (multitest()) cin >> TEST;
    while (TEST--) Nguyen_Tuong_Duy();
    time_and_memory();
}

bool multitest() {
    return 0;
}

const int N = 2005;

int n, m;
int a[N][N], num, id[N][N];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int lab[N * N], val[N * N], l[N * N], r[N * N];
bool vis[N * N];
int c[N][N];
int dp[N], cur[N];

void init() {
    memset(lab, -1, sizeof(lab));
}

bool in(int x, int y) {
    return 1 <= x && x <= n && 1 <= y && y <= m;
}

int find(int u) {
    return lab[u] < 0 ? u : lab[u] = find(lab[u]);
}

void merge(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) return;
    if (lab[u] > lab[v]) swap(u, v);
    lab[u] += lab[v];
    val[u] += val[v];
    l[u] = min(l[u], l[v]);
    r[u] = max(r[u], r[v]);
    lab[v] = u;
}

int C(int i, int j) {
    return c[i + 1][j] - c[j + 1][j];
}

void dnc(int l, int r, int x, int y) {
    if (l > r) return;
    int mid = (l + r) >> 1;
    pair<int, int> best = {-1, -1};
    for (int i: range(x, min(mid, y))) best = max(best, {dp[i] + C(i, mid), i});
    cur[mid] = best.first;
    dnc(l, mid - 1, x, best.second);
    dnc(mid + 1, r, best.second, y);
}

void Nguyen_Tuong_Duy() {
    cin >> n >> m;
    for (int i: range(n)) {
        for (int j: range(m)) {
            char c;
            cin >> c;
            if (c != '.') a[i][j] = c - '0';
            else a[i][j] = -1;
            val[id[i][j] = ++num] = a[i][j];
            l[id[i][j]] = r[id[i][j]] = j;
        }
    }

    for (int i: range(n)) {
        for (int j: range(m)) {
            if (a[i][j] != -1) {
                for (int k: range(0, 3)) {
                    int x = i + dx[k];
                    int y = j + dy[k];
                    if (in(x, y) && a[x][y] != -1) merge(id[i][j], id[x][y]);
                }
            }
        }
    }

    for (int i: range(n)) {
        for (int j: range(m)) {
            if (a[i][j] != -1) {
                int u = find(id[i][j]);
                if (!vis[u]) {
                    vis[u] = 1;
                    c[l[u]][r[u]] += val[u];
                }
            }
        }
    }

    for (int i: range(m, 1, -1))
        for (int j: range(m, 1, -1))
            c[i][j] += c[i + 1][j] + c[i][j + 1] - c[i + 1][j + 1];

    for (int i: range(m)) dp[i] = C(0, i);
    cout << *max_element(dp + 1, dp + m + 1) << "\n";

    for (int j: range(m - 1)) {
        dnc(1, m, 0, m);
        for (int i: range(m)) dp[i] = cur[i];
        cout << *max_element(dp + 1, dp + m + 1) << "\n";
    }
}

bool END;
void time_and_memory() {
    cerr << "\nUsed: " << clock() - TIME << " ms, ";
    cerr << fixed << setprecision(3);
    cerr << fabs((&START - &END) / 1048576.0) << " MB\n\n";
}

Compilation message

nafta.cpp: In function 'void Nguyen_Tuong_Duy()':
nafta.cpp:142:14: warning: unused variable 'j' [-Wunused-variable]
  142 |     for (int j: range(m - 1)) {
      |              ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 17752 KB Output is correct
2 Correct 5 ms 17756 KB Output is correct
3 Correct 5 ms 17824 KB Output is correct
4 Correct 5 ms 17752 KB Output is correct
5 Correct 4 ms 17756 KB Output is correct
6 Correct 4 ms 17756 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 17752 KB Output is correct
2 Correct 5 ms 17756 KB Output is correct
3 Correct 5 ms 17824 KB Output is correct
4 Correct 5 ms 17752 KB Output is correct
5 Correct 4 ms 17756 KB Output is correct
6 Correct 4 ms 17756 KB Output is correct
7 Correct 11 ms 23044 KB Output is correct
8 Correct 11 ms 22988 KB Output is correct
9 Correct 11 ms 23128 KB Output is correct
10 Correct 10 ms 23132 KB Output is correct
11 Correct 10 ms 23132 KB Output is correct
12 Correct 10 ms 23132 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 17752 KB Output is correct
2 Correct 5 ms 17756 KB Output is correct
3 Correct 5 ms 17824 KB Output is correct
4 Correct 5 ms 17752 KB Output is correct
5 Correct 4 ms 17756 KB Output is correct
6 Correct 4 ms 17756 KB Output is correct
7 Correct 11 ms 23044 KB Output is correct
8 Correct 11 ms 22988 KB Output is correct
9 Correct 11 ms 23128 KB Output is correct
10 Correct 10 ms 23132 KB Output is correct
11 Correct 10 ms 23132 KB Output is correct
12 Correct 10 ms 23132 KB Output is correct
13 Correct 235 ms 117988 KB Output is correct
14 Correct 272 ms 118100 KB Output is correct
15 Correct 277 ms 117964 KB Output is correct
16 Correct 200 ms 118344 KB Output is correct
17 Correct 187 ms 118100 KB Output is correct
18 Correct 185 ms 118100 KB Output is correct