oj.uz

Submission #422266

# Submission time Handle Problem Language Result Execution time Memory
422266 2021-06-10T00:09:25 Z Odavey Nafta (COI15_nafta) C++14
100 / 100
 578 ms 114760 KB 
//
// ~oisín~ C++ Template
//

#include                <bits/stdc++.h>
#define MX_N            2003
#define MX_F            2000006
#define mp              make_pair
#define mod7            1000000007
#define modpi           314159
#define PI              3.141592653589793238
#define pb              push_back
#define FastIO          ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define All(a)          a.begin(),a.end()
#define fi              first
#define se              second
#define ll              long long int
#define ull             unsigned long long int

int kx[8]  =            {+2, +2, -2, -2, +1, +1, -1, -1};
int ky[8]  =            {+1, -1, +1, -1, +2, -2, +2, -2};
int d9x[9] =            {+1, +1, +1, +0, +0, +0, -1, -1, -1};
int d9y[9] =            {+1, +0, -1, +1, +0, -1, +1, +0, -1};
int dx4[4] =            {+0, +0, +1, -1};
int dy4[4] =            {+1, -1, +0, +0};

ll gcd(ull a, ull b){
    return (a==0)?b:gcd(b%a,a);
}

ll lcm(ull a, ull b){
    return a*(b/gcd(a,b));
}

const long long INF = 1e18;

using namespace std;

int Rows, Cols;
int field[MX_N][MX_N];
int p[MX_N][MX_N];
int op[MX_N][MX_N], o[MX_N][MX_N];
int L[MX_F], R[MX_F], V[MX_F];
int pool[MX_N];
int F = 0;

bool valid(int x, int y){
    if(x < 0 || x >= Cols || y < 0 || y >= Rows){
        return false;
    }
    if(p[y][x] != -1 || field[y][x] == -1){
        return false;
    }
    return true;
}

void flood(int x, int y){
    L[F] = min(L[F], x);
    R[F] = max(R[F], x);
    V[F] += field[y][x];
    p[y][x] = F;
    for(int i=0;i<4;++i){
        if(valid(x+dx4[i], y+dy4[i])){
            flood(x+dx4[i], y+dy4[i]);
        }
    }
    return;
}

int dp[MX_N], _dp[MX_N];

void round(int l, int r, int optl, int optr){
    if(l > r){
        return;
    }
    int m = (l+r)/2;
    _dp[m] = dp[optl] - o[m][optl] + pool[m];
    int opt = optl;
    for(int i=optl;i<=optr && i<m;++i){
        if(dp[i] - o[m][i] + pool[m] > _dp[m]){
            _dp[m] = dp[i] - o[m][i] + pool[m];
            opt = i;
        }
    }
    round(l, m-1, optl, opt);
    round(m+1, r, opt, optr);
    return;
}

int main(){
    cin >> Rows >> Cols;
    char tmp_char;
    memset(op, 0, sizeof(op));
    memset(o, 0, sizeof(o));
    memset(p, -1, sizeof(p));
    memset(field, -1, sizeof(field));
    for(int i=0;i<Rows;++i){
        for(int j=0;j<Cols;++j){
            cin >> tmp_char;
            if(tmp_char != '.'){
                field[i][j] = tmp_char - '0';
            }
        }
    }
    for(int i=0;i<Rows;++i){
        for(int j=0;j<Cols;++j){
            if(p[i][j] == -1 && field[i][j] != -1){
                L[F] = j;
                R[F] = j;
                V[F] = 0;
                flood(j, i);
                ++F;
            }
        }
    }

    for(int f=0;f<F;++f){
        op[L[f]][L[f]] += V[f];
        if(R[f] < Cols-1){
            op[R[f]+1][R[f]+1] += V[f];
            op[R[f]+1][L[f]] -= V[f];
            op[L[f]][R[f]+1] -= V[f];
        }
    }
    for(int i=0;i<Cols;++i){
        for(int j=0;j<Cols;++j){
            o[i][j] += op[i][j];
            if(j){
                o[i][j] += o[i][j-1];
            }
            if(i){
                o[i][j] += o[i-1][j];
            }
            if(i && j){
                o[i][j] -= o[i-1][j-1];
            }
        }
    }

    memset(pool, 0, sizeof(pool));
    for(int f=0;f<F;++f){
        for(int i=L[f];i<=R[f];++i){
            pool[i] += V[f];
        }
    }
    for(int k=0;k<Cols;++k){
        if(k == 0){
            memcpy(_dp, pool, sizeof(_dp));
        }else{
            round(k, Cols-1, k-1, Cols-1);
//            for(int i=k;i<Cols;++i){
//                for(int j=k-1;j<i;++j){
//                    _dp[i] = max(_dp[i], dp[j] - o[i][j] + pool[i]);
//                }
//            }
        }
        int best = 0;
        for(int i=0;i<Cols;++i){
            best = max(best, _dp[i]);
        }
        cout << best << endl;
        memcpy(dp, _dp, sizeof(_dp));
        memset(_dp, 0, sizeof(_dp));
    }
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 63052 KB Output is correct
2 Correct 26 ms 63056 KB Output is correct
3 Correct 27 ms 63104 KB Output is correct
4 Correct 28 ms 63052 KB Output is correct
5 Correct 28 ms 63044 KB Output is correct
6 Correct 27 ms 63120 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 63052 KB Output is correct
2 Correct 26 ms 63056 KB Output is correct
3 Correct 27 ms 63104 KB Output is correct
4 Correct 28 ms 63052 KB Output is correct
5 Correct 28 ms 63044 KB Output is correct
6 Correct 27 ms 63120 KB Output is correct
7 Correct 37 ms 63280 KB Output is correct
8 Correct 38 ms 63208 KB Output is correct
9 Correct 41 ms 64332 KB Output is correct
10 Correct 35 ms 63308 KB Output is correct
11 Correct 37 ms 63244 KB Output is correct
12 Correct 36 ms 63140 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 63052 KB Output is correct
2 Correct 26 ms 63056 KB Output is correct
3 Correct 27 ms 63104 KB Output is correct
4 Correct 28 ms 63052 KB Output is correct
5 Correct 28 ms 63044 KB Output is correct
6 Correct 27 ms 63120 KB Output is correct
7 Correct 37 ms 63280 KB Output is correct
8 Correct 38 ms 63208 KB Output is correct
9 Correct 41 ms 64332 KB Output is correct
10 Correct 35 ms 63308 KB Output is correct
11 Correct 37 ms 63244 KB Output is correct
12 Correct 36 ms 63140 KB Output is correct
13 Correct 450 ms 73056 KB Output is correct
14 Correct 504 ms 70116 KB Output is correct
15 Correct 578 ms 114760 KB Output is correct
16 Correct 415 ms 69956 KB Output is correct
17 Correct 402 ms 67272 KB Output is correct
18 Correct 387 ms 67268 KB Output is correct