oj.uz

Submission #500857

# Submission time Handle Problem Language Result Execution time Memory
500857 2022-01-01T12:56:46 Z naal Nafta (COI15_nafta) C++14
100 / 100
 289 ms 41680 KB 
// https://oj.uz/problem/view/COI15_nafta
#include <bits/stdc++.h>
using namespace std;

const int N = 2005;
typedef pair <int, int> ii;
#define fi first
#define se second

int n, m, sumReg, val[N], f[N][N], c[N][N];
char a[N][N];
bool vis[N][N];
int fx[] = {-1, 0, 1, 0},
    fy[] = {0, 1, 0, -1};
queue <ii> q;

ii bfs(int x, int y) {
    q.push({x, y});
    int l = y, r = y;
    vis[x][y] = 1;
    sumReg = 0;
    while (q.size()) {
        x = q.front().fi, y = q.front().se;
        q.pop();
        sumReg += a[x][y] - '0';
        for (int i = 0; i < 4; i++) {
            int nx = x + fx[i], ny = y + fy[i];
            if (!vis[nx][ny]) {
                l = min(l, ny);
                r = max(r, ny);
                vis[nx][ny] = 1;
                q.push({nx, ny});
            }
        }
    }
    return {l, r};
}

void cal(int i, int l, int r, int optL, int optR) {
    if (l > r) 
        return;
    int mid = (l + r) / 2, p;
    for (int j = optL; j <= min(mid, optR); j++)
        if (f[i][mid] < f[i - 1][j - 1] + c[j][mid]) {
            f[i][mid] = f[i - 1][j - 1] + c[j][mid];
            p = j;
        }
    cal(i, l, mid - 1, optL, p);
    cal(i, mid + 1, r, p, optR);
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    // freopen("nhap.inp", "r", stdin);
    cin >> n >> m;
    for (int i = 0; i <= m + 1; i++)
        vis[0][i] = vis[n + 1][i] = 1;
    for (int i = 0; i <= n + 1; i++)
        vis[i][0] = vis[i][m + 1] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            vis[i][j] = (a[i][j] == '.');
        }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (!vis[i][j]) {
                ii tmp = bfs(i, j);
                c[tmp.fi][tmp.se] += sumReg;
            }
    
    for (int d = m - 1; d >= 0; d--) 
        for (int i = 1; i + d <= m; i++) {
            int j = i + d;
            c[i][j] += c[i - 1][j];
        }

    for (int i = 1; i < m; i++)
        for (int j = i + 1; j <= m; j++)
            c[i][j] += c[i][j - 1];
    
    for (int i = 1; i <= m; i++) {
        cal(i, 1, m, 1, m);
        cout << f[i][m] << endl;
        // for (int j = 1; j <= m; j++)
        //     cout << f[i][j] << ' ';
    }
    return 0;
}

Compilation message

nafta.cpp: In function 'void cal(int, int, int, int, int)':
nafta.cpp:48:8: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |     cal(i, l, mid - 1, optL, p);
      |     ~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 824 KB Output is correct
2 Correct 1 ms 840 KB Output is correct
3 Correct 2 ms 836 KB Output is correct
4 Correct 1 ms 844 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 844 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 824 KB Output is correct
2 Correct 1 ms 840 KB Output is correct
3 Correct 2 ms 836 KB Output is correct
4 Correct 1 ms 844 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Correct 6 ms 4556 KB Output is correct
8 Correct 6 ms 4564 KB Output is correct
9 Correct 7 ms 4556 KB Output is correct
10 Correct 6 ms 4556 KB Output is correct
11 Correct 6 ms 4556 KB Output is correct
12 Correct 6 ms 4428 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 824 KB Output is correct
2 Correct 1 ms 840 KB Output is correct
3 Correct 2 ms 836 KB Output is correct
4 Correct 1 ms 844 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Correct 6 ms 4556 KB Output is correct
8 Correct 6 ms 4564 KB Output is correct
9 Correct 7 ms 4556 KB Output is correct
10 Correct 6 ms 4556 KB Output is correct
11 Correct 6 ms 4556 KB Output is correct
12 Correct 6 ms 4428 KB Output is correct
13 Correct 254 ms 41484 KB Output is correct
14 Correct 253 ms 41488 KB Output is correct
15 Correct 289 ms 41588 KB Output is correct
16 Correct 238 ms 41540 KB Output is correct
17 Correct 262 ms 41680 KB Output is correct
18 Correct 241 ms 41552 KB Output is correct