Submission #367713

#	Time	Username	Problem	Language	Result	Execution time	Memory
367713		Vince729	Nafta (COI15_nafta)	C++11	100 / 100	432 ms	119276 KiB

nafta

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

typedef long long ll;
typedef complex<double> pt;
typedef pair<int, int> pii;
#define x() real()
#define y() imag()
#define smx(a, b) a = max(a, b)
#define smn(a, b) a = min(a, b)
#define in(mp, v) (mp.find(v) != mp.end())
#define iter(var, n) for (int var = 0; var < n; var++)

const int MAXN = 2003;
const int MOD = 1000000007;

int R, S;
int add[MAXN][MAXN];
bool vis[MAXN][MAXN];
int num[MAXN][MAXN];
int dp[MAXN][MAXN];
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

int minC, maxC, cnt;
void ff(int r, int c) {
    smn(minC, c);
    smx(maxC, c);
    cnt += num[r][c];
    vis[r][c] = 1;
    iter(d, 4) {
        int nr = r+dx[d], nc = c+dy[d];
        if (nr >= 1 && nr <= R && nc >= 1 && nc <= S && !vis[nr][nc] && num[nr][nc] >= 0) {
            ff(nr, nc);
        }
    }
}

void solve(int k, int i, int j, int l, int r) {
    if (i > j) return;
    int mid = (i+j)/2;
    int bi = -1;
    for (int b = l; b <= min(r, mid); b++) {
        int nv = dp[k-1][b-1]+add[b-1][mid];
        if (nv > dp[k][mid]) {
            bi = b;
            dp[k][mid] = nv;
        }
    }
    solve(k, i, mid-1, l, bi);
    solve(k, mid+1, j, bi, r);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> R >> S;
    for (int i = 1; i <= R; i++) {
        string s; cin >> s;
        for (int j = 1; j <= S; j++) {
            if (s[j-1] == '.') num[i][j] = -1;
            else num[i][j] = s[j-1]-'0';
        }
    }

    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= S; j++) {
            if (num[i][j] >= 0 && !vis[i][j]) {
                minC = MOD; maxC = -1; cnt = 0;
                ff(i, j);
                for (int k = minC; k <= maxC; k++) {
                    add[0][k] += cnt;
                    add[minC][k] -= cnt;
                }
            }
        }
    }

    for (int j = 1; j <= S; j++) {
        for (int i = 1; i <= S; i++) {
            add[i][j] += add[i-1][j];
            dp[i][j] = -MOD;
        }
    }

    dp[0][0] = 0;
    for (int k = 1; k <= S; k++) {
        solve(k, 1, S, 1, S);
        int ans = -MOD;
        for (int j = 1; j <= S; j++) {
            smx(ans, dp[k][j]);
        }
        cout << ans << '\n';
    }
    return 0;
}

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