oj.uz

Submission #219999

# Submission time Handle Problem Language Result Execution time Memory
219999 2020-04-06T19:41:31 Z edsa Nafta (COI15_nafta) C++17
100 / 100
 281 ms 36412 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;
const ll MOD = 998244353;
const int INF = 1e9+9;
const int MAXN = 2003;


int R, S;
vii LE[MAXN], RE[MAXN];
string r[MAXN];
int dp[MAXN], olddp[MAXN], adp[MAXN][MAXN];

void calc_adp() {
    for (int i = 1; i <= S; ++i) {
        for (auto [L, v] : RE[i-1]) {
            adp[i-1][i] += v;
            if (L > 0) adp[L-1][i] -= v;
        }
        for (int j = i-1; j >= 0; --j) {
            adp[j][i] += adp[j+1][i];
        }
        for (int j = i-1; j >= 0; --j) {
            adp[j][i] += adp[j][i-1];
        }
    }
}

void solve(int L, int R, int optL, int optR) {
    if (R <= L) return;
    int m = (L+R)/2, opt = m;
    dp[m] = 0;
    for (int i = max(m+1, optL); i <= optR; ++i) {
        if (olddp[i]+adp[m][i] > dp[m]) {
            dp[m] = olddp[i]+adp[m][i];
            opt = i;
        }
    }
    solve(L, m, optL, opt);
    solve(m+1, R, opt, optR);
}


int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> R >> S;
    for (int i = 0; i < R; ++i) {
        cin >> r[i];
    }

    queue<ii> myq;
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < S; ++j) {
            if (r[i][j] != '.') {
                int sum = r[i][j]-'0';
                int IL = j, IR = j;
                r[i][j] = '.';
                myq.emplace(i, j);
                while (!myq.empty()) {
                    auto [ii, jj] = myq.front();
                    myq.pop();
                    static const vii mov = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
                    for (auto [vi, vj] : mov) {
                        int iii = ii+vi, jjj = jj+vj;
                        if (iii >= 0 and iii < R and
                            jjj >= 0 and jjj < S and
                            r[iii][jjj] != '.') {
                            sum += r[iii][jjj]-'0';
                            r[iii][jjj] = '.';
                            myq.emplace(iii, jjj);
                            IL = min(IL, jjj);
                            IR = max(IR, jjj);
                        }
                    }
                }
                LE[IL].emplace_back(IR, sum);
                RE[IR].emplace_back(IL, sum);
                // cerr << IL << ", " << IR << " " << sum << endl;
            }
        }
    }

    calc_adp();
    for (int k = 0; k < S; ++k) {
        for (int i = 0; i < S; ++i) {
            olddp[i] = dp[i];
        }
        solve(0, S, 0, S);
        // for (int i = 0; i <= S; ++i) {
        //     cerr << dp[i] << ' ';
        // }
        // cerr << endl;
        cout << *max_element(dp, dp+S) << '\n';
    }
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 6 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 5 ms 768 KB Output is correct
7 Correct 10 ms 2432 KB Output is correct
8 Correct 10 ms 2304 KB Output is correct
9 Correct 10 ms 2048 KB Output is correct
10 Correct 10 ms 2304 KB Output is correct
11 Correct 10 ms 2176 KB Output is correct
12 Correct 8 ms 2048 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 6 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 5 ms 768 KB Output is correct
7 Correct 10 ms 2432 KB Output is correct
8 Correct 10 ms 2304 KB Output is correct
9 Correct 10 ms 2048 KB Output is correct
10 Correct 10 ms 2304 KB Output is correct
11 Correct 10 ms 2176 KB Output is correct
12 Correct 8 ms 2048 KB Output is correct
13 Correct 254 ms 36412 KB Output is correct
14 Correct 270 ms 29944 KB Output is correct
15 Correct 281 ms 23416 KB Output is correct
16 Correct 221 ms 28920 KB Output is correct
17 Correct 180 ms 22860 KB Output is correct
18 Correct 182 ms 22776 KB Output is correct