oj.uz

Submission #934129

# Submission time Handle Problem Language Result Execution time Memory
934129 2024-02-26T20:30:04 Z sheldon Nafta (COI15_nafta) C++14
100 / 100
 279 ms 110192 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] = 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;
    int mx2 = 0;
    for (int j = 1; j <= m; ++j) {
        mx2 = max(mx2, dp[j][1]);
    }
    cout << mx2 << '\n';
    for (int i = 2; i <= m; ++i) {
        dc (1, m, 1, m, i);
        int mx = 0;
        for (int j = 1; j <= m; ++j) {
            mx = max(mx, dp[j][i]);
        }
        cout << mx << '\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
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 1 ms 8752 KB Output is correct
5 Correct 1 ms 8792 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 6 ms 13660 KB Output is correct
8 Correct 6 ms 13660 KB Output is correct
9 Correct 7 ms 15196 KB Output is correct
10 Correct 5 ms 13660 KB Output is correct
11 Correct 6 ms 13620 KB Output is correct
12 Correct 5 ms 13404 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 1 ms 8752 KB Output is correct
5 Correct 1 ms 8792 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 6 ms 13660 KB Output is correct
8 Correct 6 ms 13660 KB Output is correct
9 Correct 7 ms 15196 KB Output is correct
10 Correct 5 ms 13660 KB Output is correct
11 Correct 6 ms 13620 KB Output is correct
12 Correct 5 ms 13404 KB Output is correct
13 Correct 171 ms 50400 KB Output is correct
14 Correct 212 ms 47260 KB Output is correct
15 Correct 279 ms 110192 KB Output is correct
16 Correct 163 ms 46676 KB Output is correct
17 Correct 170 ms 43608 KB Output is correct
18 Correct 162 ms 43604 KB Output is correct