Submission #872826

#	Time	Username	Problem	Language	Result	Execution time	Memory
872826		happy	Nafta (COI15_nafta)	C++14	100 / 100	324 ms	105640 KiB

nafta

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2048;
int n, m, a[maxn][maxn], miny, maxy, sum, res, f[maxn][maxn], d[maxn], row1[maxn];
bool used[maxn][maxn];
pair <int, int> nb[4] = {{0, 1} , {1, 0} , {0, -1} , {-1, 0}};
vector <int> dp_before(maxn), dp_cur(maxn);
vector <pair <int, int> > v[maxn];

void read()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m ;
    int i, j;
    char c;
    for (i=1; i<=n; ++i)
    {
        for (j=1; j<=m; ++j)
        {
            cin >> c ;
            if (c == '.') a[i][j] = -1;
            else a[i][j] = (int)(c-'0');
        }
    }
}

void dfs(int x, int y)
{
    //cout << x << " " << y << '\n' ;
    used[x][y] = true;
    sum += a[x][y];
    if (y < miny) miny = y;
    if (y > maxy) maxy = y;

    int i, nx, ny;
    for (i=0; i<4; ++i)
    {
        nx = x + nb[i].first;
        ny = y + nb[i].second;
        if (nx > 0 && ny > 0 && nx <= n && ny <= m && (used[nx][ny] == 0) && (a[nx][ny] != -1))
            dfs(nx, ny);
    }
}

void divide(int left, int right, int optl, int optr)
{
    if (left > right) return;
    int mid = (left + right) >> 1;
    int k = min(mid, optr);
    int i, opt = -1, best = 0, t;
    for (i=optl; i<=k; ++i)
    {
        t = dp_before[i] - f[i][mid];
        if (t >= best)
        {
            best = t;
            opt = i;
        }
    }

    dp_cur[mid] = best + row1[mid];
    if (dp_cur[mid] > res) res = dp_cur[mid];
    divide(left, mid-1, optl, opt);
    divide(mid+1, right, opt, optr);
}

void solve()
{
    int i, j, l;
    for (i=1; i<=n; ++i)
    {
        for (j=1; j<=m; ++j)
        {
            if (!used[i][j] && a[i][j] != -1)
            {
                //cout << "***" << '\n' ;
                maxy = 0, miny = INT_MAX;
                sum = 0;
                dfs(i,j);

                v[miny].push_back({miny, sum});
                v[maxy+1].push_back({miny, -sum});
                for (l=miny; l<=maxy; ++l)
                {
                    dp_cur[l] += sum;
                    row1[l] += sum;
                    if (dp_cur[l] > res)
                        res = dp_cur[l];
                }
            }
        }
    }

    cout << res << '\n' ;

    int len, k;
    for (j=1; j<=m; ++j)
    {
        len = (int)(v[j].size());
        for (i=0; i<len; ++i)
            d[v[j][i].first] += v[j][i].second;

        k = 0;
        for (i=1; i<=j; ++i)
        {
            k += d[i];
            f[i][j] = k;
        }
    }

    for (l=2; l<=m; ++l)
    {
        res = 0;
        dp_before = dp_cur;
        divide(1, n, 1, n);
        cout << res << '\n' ;
    }
}

int main()
{
    read();
    solve();
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 66 / 66