Submission #971611

#	Time	Username	Problem	Language	Result	Execution time	Memory
971611		GasmaskChan	Nafta (COI15_nafta)	C++17	100 / 100	279 ms	88148 KiB

nafta

#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 / 11
• Subtask 2: 23 / 23
• Subtask 3: 66 / 66