oj.uz

Submission #872826

# Submission time Handle Problem Language Result Execution time Memory
872826 2023-11-13T22:10:03 Z happy Nafta (COI15_nafta) C++14
100 / 100
 324 ms 105640 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8792 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8732 KB Output is correct
5 Correct 2 ms 8716 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 1 ms 8792 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8732 KB Output is correct
5 Correct 2 ms 8716 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 6 ms 13660 KB Output is correct
8 Correct 7 ms 13712 KB Output is correct
9 Correct 8 ms 15132 KB Output is correct
10 Correct 6 ms 13656 KB Output is correct
11 Correct 5 ms 13400 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 1 ms 8792 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8732 KB Output is correct
5 Correct 2 ms 8716 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 6 ms 13660 KB Output is correct
8 Correct 7 ms 13712 KB Output is correct
9 Correct 8 ms 15132 KB Output is correct
10 Correct 6 ms 13656 KB Output is correct
11 Correct 5 ms 13400 KB Output is correct
12 Correct 5 ms 13404 KB Output is correct
13 Correct 237 ms 55064 KB Output is correct
14 Correct 262 ms 48660 KB Output is correct
15 Correct 324 ms 105640 KB Output is correct
16 Correct 208 ms 47152 KB Output is correct
17 Correct 180 ms 41412 KB Output is correct
18 Correct 181 ms 41280 KB Output is correct