oj.uz

Submission #412664

# Submission time Handle Problem Language Result Execution time Memory
412664 2021-05-27T09:59:33 Z hgmhc Nafta (COI15_nafta) C++17
100 / 100
 520 ms 183056 KB 
#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.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 2 ms 972 KB Output is correct
3 Correct 2 ms 1092 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 2 ms 972 KB Output is correct
6 Correct 2 ms 968 KB Output is correct
7 Correct 11 ms 5708 KB Output is correct
8 Correct 13 ms 5628 KB Output is correct
9 Correct 13 ms 8836 KB Output is correct
10 Correct 9 ms 5588 KB Output is correct
11 Correct 9 ms 5584 KB Output is correct
12 Correct 9 ms 5708 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 2 ms 972 KB Output is correct
3 Correct 2 ms 1092 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 2 ms 972 KB Output is correct
6 Correct 2 ms 968 KB Output is correct
7 Correct 11 ms 5708 KB Output is correct
8 Correct 13 ms 5628 KB Output is correct
9 Correct 13 ms 8836 KB Output is correct
10 Correct 9 ms 5588 KB Output is correct
11 Correct 9 ms 5584 KB Output is correct
12 Correct 9 ms 5708 KB Output is correct
13 Correct 369 ms 55248 KB Output is correct
14 Correct 412 ms 55172 KB Output is correct
15 Correct 520 ms 183056 KB Output is correct
16 Correct 337 ms 55196 KB Output is correct
17 Correct 451 ms 55164 KB Output is correct
18 Correct 440 ms 55216 KB Output is correct