oj.uz

Submission #971611

# Submission time Handle Problem Language Result Execution time Memory
971611 2024-04-29T04:56:04 Z GasmaskChan Nafta (COI15_nafta) C++17
100 / 100
 279 ms 88148 KB 
#include <bits/stdc++.h>

using namespace std;
#define int long long
#define MAX 2007

const int dx[] = {1, 0, 0, -1};
const int dy[] = {0, 1, -1, 0};

char a[MAX][MAX];
bool visited[MAX][MAX];
int sum[MAX], val[MAX][MAX], f[MAX][MAX];
queue<pair<int, int>> q;
vector<pair<int, int>> posi[MAX];

void dfs(int l, int r, int u, int v, int cur)
{
    if (l > r) return;
    int mid = (l + r) >> 1, best = 0;

    for (int i = u; i <= min(v, mid); i++)
        if (f[cur - 1][i - 1] + val[i][mid] > f[cur][mid])
        {
            f[cur][mid] = f[cur - 1][i - 1] + val[i][mid];
            best = i;
        }

    dfs(l, mid - 1, u, best, cur);
    dfs(mid + 1, r, best, v, cur);
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("test.in", "r", stdin); freopen("test.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
       for (int j = 1; j <= m; j++)
           cin >> a[i][j];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
           if (a[i][j] != '.' && !visited[i][j])
           {
               int l = j, r = j, s = 0;
               visited[i][j] = true;
               q.emplace(i, j);

               while (!q.empty())
               {
                   int u, v;
                   tie(u, v) = q.front();
                   q.pop();

                   l = min(l, v), r = max(r, v);
                   s += a[u][v] - 48;

                   for (int x, y, k = 0; k < 4; k++)
                   {
                       x = u + dx[k], y = v + dy[k];
                       if (min(x, y) > 0 && x <= n && y <= m && a[x][y] != '.' && !visited[x][y])
                       {
                           visited[x][y] = true;
                           q.emplace(x, y);
                       }
                   }
               }

               posi[r].emplace_back(l, s);
           }

    for (int i = 1; i <= m; i++)
    {
        for (auto &[l, s] : posi[i])
            for (int j = l; j <= i; j++)
                sum[j] += s;

        for (int j = 1; j <= i; j++) val[j][i] = sum[j];
    }

    for (int k = 1; k <= m; k++)
    {
        dfs(1, m, 1, m, k);
        cout << f[k][m] << '\n';
    }
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 1 ms 4844 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 1 ms 4844 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 6 ms 11608 KB Output is correct
8 Correct 8 ms 11352 KB Output is correct
9 Correct 7 ms 11352 KB Output is correct
10 Correct 6 ms 11356 KB Output is correct
11 Correct 6 ms 11356 KB Output is correct
12 Correct 6 ms 11100 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 1 ms 4844 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 6 ms 11608 KB Output is correct
8 Correct 8 ms 11352 KB Output is correct
9 Correct 7 ms 11352 KB Output is correct
10 Correct 6 ms 11356 KB Output is correct
11 Correct 6 ms 11356 KB Output is correct
12 Correct 6 ms 11100 KB Output is correct
13 Correct 238 ms 88148 KB Output is correct
14 Correct 267 ms 81756 KB Output is correct
15 Correct 279 ms 75092 KB Output is correct
16 Correct 190 ms 80720 KB Output is correct
17 Correct 208 ms 74576 KB Output is correct
18 Correct 202 ms 74576 KB Output is correct