oj.uz

Submission #989046

# Submission time Handle Problem Language Result Execution time Memory
989046 2024-05-27T10:54:26 Z vjudge1 Nafta (COI15_nafta) C++17
0 / 100
 104 ms 35668 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]);
}

bool merge(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) return 0;
    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;
    return 1;
}

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(4)) {
                    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:143:14: warning: unused variable 'j' [-Wunused-variable]
  143 |     for (int j: range(m - 1)) {
      |              ^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 104 ms 35668 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 104 ms 35668 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Runtime error 104 ms 35668 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -