Submission #479909

#	Time	Username	Problem	Language	Result	Execution time	Memory
479909		cookiemonster04	Nafta (COI15_nafta)	C++17	0 / 100	1 ms	1100 KiB

nafta

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define MOD 1000000007

/* Date: 10/13/21
 * Link: https://oj.uz/problem/view/COI15_nafta
 * Verdict: WA
 */

int R, S;

bool visited[2001][2001];
int grid[2001][2001];
LL gain[2001][2001];

vector<pii> delta[2001];

LL column_sum[2001];

LL dp[2001][2001];

void solve(int layer, int solve_start, int solve_end, int check_start, int check_end) {
    if (solve_start > solve_end) return;
    int mid = (solve_start + solve_end)/2;
    LL best_val = -1; int cur_best = -1;
    for (int i = check_start; i <= min(mid, check_end); i++) {
        LL cur_val = dp[layer-1][i] + gain[i][mid];
        if (cur_val > best_val) {
            best_val = cur_val; cur_best = i;
        }
    }
    dp[layer][mid] = best_val;
    solve(layer, solve_start, mid-1, check_start, cur_best);
    solve(layer, mid+1, solve_end, cur_best, check_end);
}

int main() {
    ios::sync_with_stdio(0);
    cin >> R >> S;
    string str;
    getline(cin, str);
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < S; j++) {
            visited[i][j] = false;
            grid[i][j] = 0;
            gain[i][j] = 0;
            dp[i][j] = 0;
        }
    }
    for (int i = 0; i < S; i++) {
        column_sum[i] = 0;
    }
    for (int i = 0; i < R; i++) {
        getline(cin, str);
        for (int j = 0; j < S; j++) {
            if (str[j] == '.') {
                grid[i][j] = -1;
                visited[i][j] = true;
            } else {
                grid[i][j] = str[j]-'0';
            }
        }
    }
    
    vector<pii> q;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < S; j++) {
            if (!visited[i][j]) {
                LL size = 0;
                q.pb(mp(i, j));
                visited[i][j] = true;
                int minc = j, maxc = j;
                while(q.size() > 0) {
                    pii cur = q.back(); q.pop_back();
                    int cr = cur.first, cc = cur.second;
                    size += grid[cr][cc];
                    minc = min(minc, cc); maxc = max(maxc, cc);
                    if (cr != 0 && !visited[cr-1][cc]) {
                        visited[cr-1][cc] = true;
                        q.pb(mp(cr-1, cc));
                    }
                    if (cr != R-1 && !visited[cr+1][cc]) {
                        visited[cr+1][cc] = true;
                        q.pb(mp(cr+1, cc));
                    }
                    if (cc != 0 && !visited[cr][cc-1]) {
                        visited[cr][cc-1] = true;
                        q.pb(mp(cr, cc-1));
                    }
                    if (cc != S-1 && !visited[cr][cc+1]) {
                        visited[cr][cc+1] = true;
                        q.pb(mp(cr, cc+1));
                    }
                }
                delta[minc].pb(mp(maxc, size));
                for (int column = minc; column <= maxc; column++) {
                    column_sum[column] += size;
                }
            }
        }
    }
    for (int i = 0; i < S; i++) sort(delta[i].begin(), delta[i].end());

    for (int i = 0; i < S; i++) {
        LL remove = column_sum[i];
        int delta_ptr = 0;
        for (int j = i; j < S; j++) {
            gain[i][j] = column_sum[j] - remove;
            while(delta_ptr != delta[i].size() && delta[i][delta_ptr].first == j) {
                remove -= delta[i][delta_ptr].second;
                delta_ptr++;
            }
        }
    }
    for (int i = 0; i < S; i++) dp[1][i] = column_sum[i];
    for (int i = 2; i <= S; i++) {
        solve(i, 0, S-1, 0, S-1);
    }
    for (int i = 1; i <= S; i++) {
        LL cmax = -1;
        for (int j = 0; j < S; j++) {
            cmax = max(cmax, dp[i][j]);
        }
        cout << cmax << endl;
    }
    return 0;
}

Compilation message (stderr)

nafta.cpp: In function 'int main()':
nafta.cpp:113:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |             while(delta_ptr != delta[i].size() && delta[i][delta_ptr].first == j) {
      |                   ~~~~~~~~~~^~~~~~~~~~~~~~~~~~

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