Submission #934129

#	Time	Username	Problem	Language	Result	Execution time	Memory
934129		sheldon	Nafta (COI15_nafta)	C++14	100 / 100	279 ms	110192 KiB

nafta

#include <bits/stdc++.h>

using namespace std;

const int nax = 2005;

int C[nax][nax], n, m , win[nax], dp[nax][nax];
bool visited[nax][nax], used[(int) 1e6];
char grid[nax][nax];
vector<pair<int, int>> beg[nax], ending[nax];

vector<int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
pair<int, int> p;
int got = 0;
void dfs (int i, int j) {
    p.first = min(p.first, j);
    p.second = max(p.second, j);
    visited[i][j] = 1;
    got += grid[i][j] - '0';
    for (int k = 0; k < 4; ++k) {
        int ni = i + dx[k];
        int nj = j + dy[k];
        if (ni >= 1 && ni <= n && nj <= m && nj >= 1 && grid[ni][nj] != '.' && !visited[ni][nj]) {
            dfs (ni, nj);
        }
    }
}



void dc (int l, int r, int optl, int optr, int k) {
    if (l > r) {
        return;
    }
    int mid = (l + r) / 2;
    pair<int, int> best = {-1e9, -1};
    for (int i = optl; i <= min(mid, optr); ++i) {
        if (dp[i][k - 1] + C[i][mid] > best.first) {
            best.first = dp[i][k - 1] + C[i][mid];
            best.second = i;
        }
    }
    dp[mid][k] = best.first;
    dc (l, mid - 1, optl, best.second, k);
    dc (mid + 1, r, best.second, optr, k);
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> grid[i][j];
        }
    }
    int idx = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (!visited[i][j] && grid[i][j] != '.') {
                p = {1e9, -1e9};
                got = 0;
                dfs (i, j);
                beg[p.first].push_back({got, p.second});
                win[p.first] += got;
                win[p.second + 1] -= got;
            }
        }
    }
    int have = 0;
    for (int i = 1; i <= m; ++i) {
        have += win[i];
        dp[i][1] = have;
    }
    for (int j = 1; j <= m; ++j) {
        for (auto &it : beg[j]) {
            win[it.second + 1] += it.first;
        }
        int have2 = 0;
        for (int col2 = j + 1; col2 <= m; ++col2) {
            have2 += win[col2];
            C[j][col2] = have2;
        }
    }
    // for (int i = 1; i <= m; ++i) {
    //     for (int j = i + 1; j <= m; ++j) {
    //         // cout << i << ' ' << j << ' ' << C[i][j] << '\n';
    //     }
    // }
    // // return;
    int mx2 = 0;
    for (int j = 1; j <= m; ++j) {
        mx2 = max(mx2, dp[j][1]);
    }
    cout << mx2 << '\n';
    for (int i = 2; i <= m; ++i) {
        dc (1, m, 1, m, i);
        int mx = 0;
        for (int j = 1; j <= m; ++j) {
            mx = max(mx, dp[j][i]);
        }
        cout << mx << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}

Compilation message (stderr)

nafta.cpp: In function 'void solve()':
nafta.cpp:55:9: warning: unused variable 'idx' [-Wunused-variable]
   55 |     int idx = 1;
      |         ^~~

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