Submission #704816

#	Time	Username	Problem	Language	Result	Execution time	Memory
704816		kelfert	Nafta (COI15_nafta)	C++17	34 / 100	1062 ms	59276 KiB

nafta

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#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 F first
#define S second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::milliseconds>
(std::chrono::system_clock::now().time_since_epoch()).count());

const ll MOD = 1e9 + 7;
const int INF = 2e9;
const int N = 2010;

int cost[N][N], used[N][N], a[N][N];
 
vector<vector<int> > dp;
 
void divide(int j, int l, int r, int ql, int qr) {
    if (l >= r) return;
    int m = (l + r) / 2;
    int opt;
    for (int i = ql; i < min(m, qr); i++) {
        if (dp[j][m] < dp[j - 1][i] + cost[i][m]) {
            dp[j][m] = dp[j - 1][i] + cost[i][m];
            opt = i;
        }
    }
    //cout << j << " " << m << " " << dp[j][m] << "\n";
    divide(j, l, m, ql, opt + 1);
    divide(j, m + 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 Seg {
    int l, r, sum;
    Seg(int l, int r, int sum) : l(l), r(r), sum(sum) {}
    Seg() {}
};

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;
    for (int i = 1; i <= n; i++) {
        string s; 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);
    vector<int> cnt2(m + 1);
    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;
        //cout << l << " " << first << endl;
        for (int r = l; r <= m; r++) {
            //cout << " " << r << endl;
            while (i < events.size() && events[i].x < r) {
                //cout << "  " << i << " " << events[i].x << " " << events[i].sum << endl;
                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;
            //cout << " " << l << " " << r << " " << cost[l][r] << endl;
        }
    }
    dp.resize(m + 1, vector<int> (m + 1, -INF));
    dp[0][0] = 0;
    for (int j = 1; j <= m; j++) {
        divide(j, 0, m + 1, 0, m + 1);
        int ans = 0;
        for (int i = 1; i <= m; i++) ans = max(ans, dp[j][i]);
        cout << ans << "\n";
    }
    
    return 0;
}

Compilation message (stderr)

nafta.cpp: In function 'int main()':
nafta.cpp:121:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |         while (first < events.size() && events[first].x <= l) first++;
      |                ~~~~~~^~~~~~~~~~~~~~~
nafta.cpp:126:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |             while (i < events.size() && events[i].x < r) {
      |                    ~~^~~~~~~~~~~~~~~
nafta.cpp: In function 'void divide(int, int, int, int, int)':
nafta.cpp:49:11: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |     divide(j, l, m, ql, opt + 1);
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 0 / 66