Submission #704822

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
704822	2023-03-03T04:37:17 Z	kelfert	Nafta (COI15_nafta)	C++17	Compilation error	0 ms	0 KB

nafta

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <iomanip>
#include <queue>
#include <stack>
#include <random>
#include <chrono>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define pb emplace_back
#define all(x) (x).begin(), (x).end()
typedef long long ll;

const int INF = 2e9;
const int N = 2001;

int cost[N][N], used[N][N], a[N][N], dp[N][N], cnt2[N];
int opt, mid; 

void divide(int j, int l, int r, int ql, int qr) {
    if (l >= r) return;
    mid = (l + r) / 2;
    for (int i = ql; i < min(mid, qr); i++) {
        if (dp[j][mid] < dp[j - 1][i] + cost[i][mid]) {
            dp[j][mid] = dp[j - 1][i] + cost[i][mid];
            opt = i;
        }
    }
    divide(j, l, mid, ql, opt + 1);
    divide(j, mid + 1, r, opt, qr);
}

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

void dfs(int vx, int vy, int &sum, int &l, int &r) {
    used[vx][vy] = 1;
    sum += a[vx][vy];
    l = min(l, vy);
    r = max(r, vy);
    for (int k = 0; k < 4; k++) {
        int x = vx + dx[k], y = vy + dy[k];
        if (!used[x][y] && a[x][y] != -1) {
            dfs(x, y, sum, l, r);
        }
    }
} 

const int OPEN = 1;
const int CLOSE = -1;

struct Event {
    int x, id, tp, sum;
    Event(int x, int id, int tp, int sum) : x(x), id(id), tp(tp), sum(sum) {}
    Event() {}
};

bool comp(Event a, Event b) {
    return a.x < b.x;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m; cin >> n >> m;
    for (int i = 0; i <= n + 1; i++)
        for (int j = 0; j <= m + 1; j++)
            a[i][j] = -1;
    string s;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        for (int j = 0; j < m; j++)
            if (s[j] != '.') a[i][j + 1] = (s[j] - '0');
    }
    vector<Seg> seg;
    vector<Event> events;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!used[i][j] && a[i][j] != -1) {
                int sum = 0, l = j, r = j;
                dfs(i, j, sum, l, r);
                seg.pb(Seg(l, r, sum));
                events.pb(Event(l, seg.size() - 1, OPEN, sum));
                events.pb(Event(r, seg.size() - 1, CLOSE, sum));
            }
        }
    }
    sort(all(events), comp);
    for (auto x : events) {
        if (x.tp == OPEN) cnt2[x.x] += x.sum;
    }
    int first = 0;
    for (int l = 0; l <= m; l++) {
        while (first < events.size() && events[first].x <= l) first++;
        int i = first, sum = 0;
        for (int r = l; r <= m; r++) {
            while (i < events.size() && events[i].x < r) {
                if (events[i].tp == OPEN) {
                    sum += events[i].sum;
                } else {
                    if (seg[events[i].id].l > l) sum -= events[i].sum;
                }
                i++;    
            }
            cost[l][r] = sum + cnt2[r];
            if (l == r) cost[l][r] = 0;
        }
    }
    for (int i = 0; i <= m; i++) 
        for (int j = 0; j <= m; j++) 
            dp[i][j] = -INF;
    dp[0][0] = 0;
    int ans = 0;
    for (int j = 1; j <= m; j++) {
        divide(j, 0, m + 1, 0, m + 1);
        ans = 0;
        for (int i = 1; i <= m; i++) ans = max(ans, dp[j][i]);
        cout << ans << "\n";
    }
    
    return 0;
}

Compilation message

nafta.cpp: In function 'int main()':
nafta.cpp:87:12: error: 'Seg' was not declared in this scope
   87 |     vector<Seg> seg;
      |            ^~~
nafta.cpp:87:15: error: template argument 1 is invalid
   87 |     vector<Seg> seg;
      |               ^
nafta.cpp:87:15: error: template argument 2 is invalid
nafta.cpp:22:12: error: request for member 'emplace_back' in 'seg', which is of non-class type 'int'
   22 | #define pb emplace_back
      |            ^~~~~~~~~~~~
nafta.cpp:94:21: note: in expansion of macro 'pb'
   94 |                 seg.pb(Seg(l, r, sum));
      |                     ^~
nafta.cpp:95:40: error: request for member 'size' in 'seg', which is of non-class type 'int'
   95 |                 events.pb(Event(l, seg.size() - 1, OPEN, sum));
      |                                        ^~~~
nafta.cpp:96:40: error: request for member 'size' in 'seg', which is of non-class type 'int'
   96 |                 events.pb(Event(r, seg.size() - 1, CLOSE, sum));
      |                                        ^~~~
nafta.cpp:106:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         while (first < events.size() && events[first].x <= l) first++;
      |                ~~~~~~^~~~~~~~~~~~~~~
nafta.cpp:109:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |             while (i < events.size() && events[i].x < r) {
      |                    ~~^~~~~~~~~~~~~~~
nafta.cpp:113:28: error: invalid types 'int[int]' for array subscript
  113 |                     if (seg[events[i].id].l > l) sum -= events[i].sum;
      |                            ^