Submission #412664

#	Time	Username	Problem	Language	Result	Execution time	Memory
412664		hgmhc	Nafta (COI15_nafta)	C++17	100 / 100	520 ms	183056 KiB

nafta

#include <bits/stdc++.h>
#define REP(i,a,b) for (int i = (a); i <= (b); ++i)
#define PER(i,a,b) for (int i = (b); i >= (a); --i)
#define log2(x) (31-__builtin_clz(x))
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
#define debug(x) cout << #x << " is " << x << endl
#define endl '\n'
using namespace std; using ll = long long; using ii = pair<int,int>; using iii = tuple<int,int,int>;
void solution(); int main() {
    ios::sync_with_stdio(0); cin.tie(0); solution();
}
using ci = complex<int>;
const ci d4[] {{0,1},{1,0},{0,-1},{-1,0}}, d8[] {{0,1},{1,0},{0,-1},{-1,0}, {1,1},{1,-1},{-1,1},{-1,-1}};
#define R real()
#define C imag()
#define P(x) (x).R][(x).C
const int N = 2003;
int n, m, b[N][N], dp[N][N], p[N][N];
bool visited[N][N];

inline int cost(int s, int e) {
    return p[e][e]-p[s][e];
}
void compute(int i, ii K, ii J) {
    if (J.first > J.second) return;
    int z = (J.first+J.second)>>1, p;
    dp[i][z] = 0;
    REP(k,K.first,K.second) {
        if (k >= z) break;
        if (int c = cost(k,z); dp[i][z] < dp[i-1][k]+c) {
            dp[i][z] = dp[i-1][k]+c;
            p = k;
        }
    }
    compute(i,{K.first,p},{J.first,z-1});
    compute(i,{p,K.second},{z+1,J.second});
}

bool canGo(ci s) {
return 1 <= s.R && s.R <= n && 1 <= s.C && s.C <= m && b[P(s)] != -1 && !visited[P(s)];}
iii dfs(ci s) {
    visited[P(s)] = true;
    int o = 0, x = s.C, y = s.C;
    for (auto d : d4) if (canGo(s+d)) {
        auto [l,r,z] = dfs(s+d);
        o += z;
        x = min(l,x);
        y = max(r,y);
    }
    return {x,y,o+b[P(s)]};
}
void floodFill() {
    REP(i,1,n) REP(j,1,m) {
        if (canGo({i,j})) {
            auto[l,r,x] = dfs({i,j});
            p[l][l] += x; p[r+1][r+1] += x;
            p[r+1][l] -= x; p[l][r+1] -= x;
        }
    }
}

void input() {
    cin >> n >> m;
    REP(i,1,n) REP(j,1,m) {
        char c; cin >> c;
        if (c == '.') b[i][j] = -1;
        else b[i][j] = c-'0';
    }
}
void solution() {
    input();
    floodFill();
    REP(i,1,m) REP(j,1,m) {
        p[i][j] += p[i-1][j]+p[i][j-1]-p[i-1][j-1];
    }
    REP(i,1,m) {
        compute(i,{0,m-1},{1,m});
        cout << *max_element(dp[i],dp[i]+m+1) << endl;
    }
}

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