Submission #422266

#	Time	Username	Problem	Language	Result	Execution time	Memory
422266		Odavey	Nafta (COI15_nafta)	C++14	100 / 100	578 ms	114760 KiB

nafta

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