Submission #1093184

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093184		_callmelucian	Nafta (COI15_nafta)	C++14	100 / 100	305 ms	177496 KiB

nafta

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 4e6 + 6;
int cost[2020][2020], grp[2020][2020], dp[2][2020], L[mn], sum[mn];
bool vis[2020][2020];
char ch[2020][2020];
int n, m;

const int dr[4] = {-1, 0, 0, 1};
const int dc[4] = {0, -1, 1, 0};

bool ok (int i, int j) {
    if (i < 1 || j < 1) return 0;
    if (i > n || j > m) return 0;
    return 1;
}

void dfs (int i, int j, int gr) {
    L[gr] = min(L[gr], j), sum[gr] += ch[i][j] - '0';
    grp[i][j] = gr, vis[i][j] = 1;
    for (int k = 0; k < 4; k++) {
        int i2 = i + dr[k], j2 = j + dc[k];
        if (ok(i2, j2) && ch[i2][j2] != '.' && !vis[i2][j2]) dfs(i2, j2, gr);
    }
}

void solve (int t, int a, int b, int optL, int optR) {
    int cur = (a + b) >> 1, opt = 0;
    for (int re = optL; re <= min(cur - 1, optR); re++) {
        if (dp[t ^ 1][re] == INT_MIN) continue;
        int cand = dp[t ^ 1][re] + cost[cur][re];
        if (cand > dp[t][cur])
            dp[t][cur] = cand, opt = re;
    }

    if (a < cur) solve(t, a, cur - 1, optL, opt);
    if (cur < b) solve(t, cur + 1, b, opt, optR);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) cin >> ch[i][j];

    for (int i = 1; i <= n * m; i++) L[i] = INT_MAX;

    int counter = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (!vis[i][j] && ch[i][j] != '.') dfs(i, j, ++counter);

    for (int j = 1; j <= m; j++) {
        vector<int> cand;
        for (int i = 1; i <= n; i++)
            if (grp[i][j]) cand.push_back(grp[i][j]);
        sort(all(cand)); filter(cand);
        sort(all(cand), [&] (int a, int b) { return L[a] < L[b]; });

        int curSum = 0;
        for (int k = j - 1; k >= 0; k--) {
            while (cand.size() && k < L[cand.back()]) {
                curSum += sum[cand.back()];
                cand.pop_back();
            }
            cost[j][k] = curSum;
        }
    }

    for (int i = 1; i <= m; i++) dp[0][i] = INT_MIN;

    for (int ttimes = 1; ttimes <= m; ttimes++) {
        int t = ttimes & 1;
        for (int i = 0; i <= m; i++) dp[t][i] = INT_MIN;
        solve(t, 1, m, 0, m - 1);

        cout << *max_element(dp[t] + 1, dp[t] + 1 + m) << "\n";
    }

    return 0;
}

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