oj.uz

Submission #934125

# Submission time Handle Problem Language Result Execution time Memory
934125 2024-02-26T20:24:23 Z sheldon Nafta (COI15_nafta) C++14
0 / 100
 2 ms 7000 KB 
#include <bits/stdc++.h>

using namespace std;

const int nax = 2005;

int C[nax][nax], n, m , win[nax], dp[nax][nax];
bool visited[nax][nax], used[(int) 1e6];
char grid[nax][nax];
vector<pair<int, int>> beg[nax], ending[nax];

vector<int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
pair<int, int> p;
int got = 0;
void dfs (int i, int j) {
    p.first = min(p.first, j);
    p.second = max(p.second, j);
    visited[i][j] = 1;
    got += grid[i][j] - '0';
    for (int k = 0; k < 4; ++k) {
        int ni = i + dx[k];
        int nj = j + dy[k];
        if (ni >= 1 && ni <= n && nj <= m && nj >= 1 && grid[ni][nj] != '.' && !visited[ni][nj]) {
            dfs (ni, nj);
        }
    }
}



void dc (int l, int r, int optl, int optr, int k) {
    if (l > r) {
        return;
    }
    int mid = (l + r) / 2;
    pair<int, int> best = {-1e9, -1};
    for (int i = optl; i <= min(mid, optr); ++i) {
        if (dp[i][k - 1] + C[i][mid] > best.first) {
            best.first = dp[i][k - 1] + C[i][mid];
            best.second = i;
        }
    }
    dp[mid][k] = best.first;
    dc (l, mid - 1, optl, best.second, k);
    dc (mid + 1, r, best.second, optr, k);
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> grid[i][j];
        }
    }
    int idx = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (!visited[i][j] && grid[i][j] != '.') {
                p = {1e9, -1e9};
                got = 0;
                dfs (i, j);
                beg[p.first].push_back({got, p.second});
                win[p.first] += got;
                win[p.second + 1] -= got;
            }
        }
    }
    int have = 0;
    for (int i = 1; i <= m; ++i) {
        have += win[i];
        dp[i][1] = max(dp[i - 1][1], have);
    }
    for (int j = 1; j <= m; ++j) {
        for (auto &it : beg[j]) {
            win[it.second + 1] += it.first;
        }
        int have2 = 0;
        for (int col2 = j + 1; col2 <= m; ++col2) {
            have2 += win[col2];
            C[j][col2] = have2;
        }
    }
    // for (int i = 1; i <= m; ++i) {
    //     for (int j = i + 1; j <= m; ++j) {
    //         // cout << i << ' ' << j << ' ' << C[i][j] << '\n';
    //     }
    // }
    // // return;
    for (int i = 2; i <= m; ++i) {
        dc (1, m, 1, m, i);
    }
    for (int i = 1; i <= m; ++i) {
        cout << dp[m][i] << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}

Compilation message

nafta.cpp: In function 'void solve()':
nafta.cpp:55:9: warning: unused variable 'idx' [-Wunused-variable]
   55 |     int idx = 1;
      |         ^~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 7000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 7000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 7000 KB Output isn't correct
2 Halted 0 ms 0 KB -