oj.uz

Submission #367713

# Submission time Handle Problem Language Result Execution time Memory
367713 2021-02-18T04:12:41 Z Vince729 Nafta (COI15_nafta) C++11
100 / 100
 432 ms 119276 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1132 KB Output is correct
2 Correct 2 ms 1132 KB Output is correct
3 Correct 1 ms 1132 KB Output is correct
4 Correct 2 ms 1132 KB Output is correct
5 Correct 2 ms 1132 KB Output is correct
6 Correct 1 ms 1132 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1132 KB Output is correct
2 Correct 2 ms 1132 KB Output is correct
3 Correct 1 ms 1132 KB Output is correct
4 Correct 2 ms 1132 KB Output is correct
5 Correct 2 ms 1132 KB Output is correct
6 Correct 1 ms 1132 KB Output is correct
7 Correct 7 ms 5740 KB Output is correct
8 Correct 8 ms 5740 KB Output is correct
9 Correct 10 ms 7276 KB Output is correct
10 Correct 7 ms 5740 KB Output is correct
11 Correct 7 ms 5740 KB Output is correct
12 Correct 7 ms 5740 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1132 KB Output is correct
2 Correct 2 ms 1132 KB Output is correct
3 Correct 1 ms 1132 KB Output is correct
4 Correct 2 ms 1132 KB Output is correct
5 Correct 2 ms 1132 KB Output is correct
6 Correct 1 ms 1132 KB Output is correct
7 Correct 7 ms 5740 KB Output is correct
8 Correct 8 ms 5740 KB Output is correct
9 Correct 10 ms 7276 KB Output is correct
10 Correct 7 ms 5740 KB Output is correct
11 Correct 7 ms 5740 KB Output is correct
12 Correct 7 ms 5740 KB Output is correct
13 Correct 337 ms 55476 KB Output is correct
14 Correct 385 ms 55296 KB Output is correct
15 Correct 432 ms 119276 KB Output is correct
16 Correct 304 ms 55532 KB Output is correct
17 Correct 354 ms 55404 KB Output is correct
18 Correct 323 ms 55404 KB Output is correct