oj.uz

Submission #201641

# Submission time Handle Problem Language Result Execution time Memory
201641 2020-02-11T14:01:38 Z stefdasca Nafta (COI15_nafta) C++14
100 / 100
 385 ms 85028 KB 
#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9

// #define fisier 1

using namespace std;

typedef long long ll;

int n, m, sum[3002][3002], sum2[3002][3002];

char mat[3002][3002];

int ox[] = {-1, 0, 1, 0};
int oy[] = {0, 1, 0, -1};

int cum[3002];
int dp[3002][3002], sp[3002][3002];
int cost(int a, int b)
{
    return sp[a][b];
}
void divide(int st, int dr, int optst, int optdr, int pz)
{
    if(st > dr || optst > optdr)
        return;
    int mid = (st + dr) / 2;
    int wht = 0;
    for(int i = min(mid, optst); i <= min(mid, optdr); ++i)
        if(dp[pz-1][i] + cum[mid] - cost(i, mid) > dp[pz][mid])
        {
            dp[pz][mid] = dp[pz-1][i] + cum[mid] - cost(i, mid);
            wht = i;
        }
    divide(st, mid-1, optst, wht, pz);
    divide(mid+1, dr, wht, optdr, pz);
}
int main()
{

    #ifdef fisier
        ifstream f("input.in");
        ofstream g("output.out");
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        cin >> (mat[i] + 1);
    int acm = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            if(mat[i][j] >= '0' && mat[i][j] <= '9')
            {
                int L = j, R = j;
                int tot = (mat[i][j] - '0');
                deque<pair<int, int> > d;
                d.pb({i, j});
                mat[i][j] = '.';
                while(!d.empty())
                {
                    pair<int, int> nod = d[0];
                    L = min(L, nod.se);
                    R = max(R, nod.se);
                    d.pop_front();
                    for(int x = 0; x <= 3; ++x)
                    {
                        int new_x = nod.fi + ox[x];
                        int new_y = nod.se + oy[x];
                        if(new_x == 0 || new_y == 0 || new_x == n+1 || new_y == m+1)
                            continue;
                        if(mat[new_x][new_y] == '.')
                            continue;
                        tot += (mat[new_x][new_y] - '0');
                        mat[new_x][new_y] = '.';
                        d.pb({new_x, new_y});
                    }
                }
                sum[L][R] += tot;
                acm += tot;
            }
    for(int i = 1; i <= m; ++i)
        for(int j = i; j <= m; ++j)
            cum[i] += sum[i][j], cum[j+1] -= sum[i][j];
    for(int i = 1; i <= m; ++i)
        for(int j = m; j >= 1; --j)
            sum2[i][j] = sum[i][j] + sum2[i][j+1];
    for(int i = 1; i <= m; ++i)
        for(int j = m; j >= 1; --j)
            sp[i][j] = sum2[i][j] + sp[i-1][j];
    for(int i = 1; i <= m; ++i)
    {
        cum[i] += cum[i-1];
        dp[1][i] = cum[i];
    }
    for(int i = 2; i <= m; ++i)
        divide(1, m, 1, m, i);
    int ans = 0;
    for(int i = 1; i <= m; ++i)
    {
        for(int j = 1; j <= m; ++j)
            ans = max(ans, dp[i][j]);
        cout << ans << '\n';
    }
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1272 KB Output is correct
2 Correct 5 ms 1272 KB Output is correct
3 Correct 5 ms 1144 KB Output is correct
4 Correct 5 ms 1272 KB Output is correct
5 Correct 5 ms 1272 KB Output is correct
6 Correct 7 ms 1144 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1272 KB Output is correct
2 Correct 5 ms 1272 KB Output is correct
3 Correct 5 ms 1144 KB Output is correct
4 Correct 5 ms 1272 KB Output is correct
5 Correct 5 ms 1272 KB Output is correct
6 Correct 7 ms 1144 KB Output is correct
7 Correct 14 ms 7032 KB Output is correct
8 Correct 13 ms 7160 KB Output is correct
9 Correct 13 ms 6904 KB Output is correct
10 Correct 13 ms 7032 KB Output is correct
11 Correct 12 ms 7032 KB Output is correct
12 Correct 11 ms 6392 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1272 KB Output is correct
2 Correct 5 ms 1272 KB Output is correct
3 Correct 5 ms 1144 KB Output is correct
4 Correct 5 ms 1272 KB Output is correct
5 Correct 5 ms 1272 KB Output is correct
6 Correct 7 ms 1144 KB Output is correct
7 Correct 14 ms 7032 KB Output is correct
8 Correct 13 ms 7160 KB Output is correct
9 Correct 13 ms 6904 KB Output is correct
10 Correct 13 ms 7032 KB Output is correct
11 Correct 12 ms 7032 KB Output is correct
12 Correct 11 ms 6392 KB Output is correct
13 Correct 385 ms 84856 KB Output is correct
14 Correct 365 ms 85028 KB Output is correct
15 Correct 351 ms 84856 KB Output is correct
16 Correct 335 ms 84856 KB Output is correct
17 Correct 325 ms 81912 KB Output is correct
18 Correct 308 ms 80380 KB Output is correct