제출 #1175995

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1175995		salmakaram22222	Nafta (COI15_nafta)	C++17	100 / 100	225 ms	100400 KiB

nafta

#include <bits/stdc++.h>

#define Pc_champs ios_base::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
using namespace std;

#define ll long long
#define int long long

int const N = 2e3 + 2, LOG = 17, N2 = 3e5 + 5, M = 1e9 + 7;
int const dx[] = {0, 0, -1, 1};
int const dy[] = {1, -1, 0, 0};
int n, m, mnj, mxj;
char grid[N][N];
bool vis[N][N];
int suf[N][N];

bool valid(int i, int j) {
    return 1 <= i and i <= n and 1 <= j and j <= m;
}

int dfs(int i, int j) {
    vis[i][j] = true;
    int ret = grid[i][j] - '0';
    mnj = min(mnj, j);
    mxj = max(mxj, j);
    for (int k = 0; k < 4; ++k) {
        int ni = i + dx[k];
        int nj = j + dy[k];
        if (valid(ni, nj) and grid[ni][nj] != '.' and !vis[ni][nj]) {
            ret += dfs(ni, nj);
        }
    }
    return ret;
}

int dp[2][N];

void solve(int lx, int rx, int l, int r, bool &sign) {
    if (lx > rx) return;
    int md = lx + rx >> 1;
    int &ret = dp[sign][md];
    int best = -1;
    ret = -1;
    for (int i = l; i <= min(md, r); ++i) {
        int cst = dp[sign ^ 1][i - 1] + suf[i][md] - suf[md + 1][md];
        if (ret < cst) ret = cst, best = i;
    }

    solve(lx, md - 1, l, best, sign);
    solve(md + 1, rx, best, r, sign);
}

void dowork() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> grid[i][j];
        }
    }

    vector<pair<int, int>> interval[m + 1];
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (grid[i][j] == '.' || vis[i][j]) continue;
            mnj = mxj = j;
            int val = dfs(i, j);
            interval[mnj].emplace_back(val, mxj);
        }
    }

    vector<int> s(m + 1);
    for (int i = m; i >= 1; --i) {
        for (auto [val, j]: interval[i]) s[j] += val;
        for (int j = m; j >= 1; --j) suf[i][j] = s[j] + suf[i][j + 1];
    }

    bool sign{};
    for (int i = 1; i <= m; ++i) {
        sign ^= 1;
        solve(i, m, i, m, sign);
        cout << *max_element(dp[sign] + 1, dp[sign] + m + 1) << '\n';
    }
}


signed main() {
    Pc_champs
    int t = 1;
    //cin >> t;
    while (t--) {
        dowork();
        cout << "\n";
    }
}

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