Submission #121970

#	Time	Username	Problem	Language	Result	Execution time	Memory
121970		BartolM	Nafta (COI15_nafta)	C++17	100 / 100	780 ms	79416 KiB

nafta

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;

const int INF=0x3f3f3f3f;
const int N=2005;

int n, m;
int mat[N][N];
queue <pii> Q;
int bio[N][N];
int dx[4]={-1, 0, 1, 0};
int dy[4]={0, 1, 0, -1};
vector <pii> L[N], R[N];
int val[N][N], uk[N], stup[N];
int dp[N][N];

bool check(int x, int y) {
    return x>=0 && y>=0 && y<m && x<n;
}

void bfs(int x, int y) {
    Q.push(mp(x, y));
    bio[x][y]=1;
    int sum=0, ll=y, rr=y;
    while (!Q.empty()) {
        pii pp=Q.front();
        Q.pop();
        ll=min(ll, pp.Y);
        rr=max(rr, pp.Y);
        sum+=mat[pp.X][pp.Y];
        for (int i=0; i<4; ++i) {
            int px=pp.X+dx[i], py=pp.Y+dy[i];
            if (check(px, py) && mat[px][py]!=-1 && !bio[px][py]) {
                Q.push(mp(px, py));
                bio[px][py]=1;
            }
        }
    }
    //printf("[%d, %d] -> %d\n", ll, rr, sum);
    L[ll].pb(mp(rr, sum));
    R[rr+1].pb(mp(ll, sum));
}

void prec() {
    for (int i=0; i<m; ++i) {
        for (pii x:L[i]) {
            uk[i]+=x.Y;
        }
        stup[i]=uk[i];
        for (pii x:R[i]) {
            uk[i]-=x.Y;
        }
        if (i!=0) uk[i]+=uk[i-1];
        //printf("%d ", uk[i]);
    }
    //printf("\n");
    for (int i=0; i<m; ++i) {
        sort(R[i].begin(), R[i].end());
        for (int j=(int)R[i].size()-2; j>=0; --j) R[i][j].Y+=R[i][j+1].Y;
    }

    for (int i=0; i<m; ++i) {
        for (int j=i+1; j<m; ++j) {
            val[i][j]=stup[j];
            val[i][j]+=val[i][j-1];

            vector <pii>::iterator it=lower_bound(R[j].begin(), R[j].end(), mp(i+1, -1));
            int ind=it-R[j].begin();

            if (it!=R[j].end()) val[i][j]-=R[j][ind].Y;
            //printf("val[%d][%d] == %d\n", i, j, val[i][j]);
        }
    }
}

void rek(int lo, int hi, int pi_lo, int pi_hi, int br) {
    if (lo>hi) return;
    int mid=(lo+hi)/2;
    int ma=-1, ind=-1;
    for (int i=pi_lo; i<=pi_hi; ++i) {
        if (i>=mid) break;
        int curr=dp[i][br-1]+val[i][mid];
        if (curr>ma) {
            ind=i;
            ma=curr;
        }
    }
    dp[mid][br]=ma;
//    printf("pivoti  === [%d, %d]\n", pi_lo, pi_hi);
//    printf("[%d, %d] ===== dp[%d][%d] == %d, pivot == %d\n", lo, hi, mid, br, ma, ind);
    if (lo<hi) {
        if (ind!=-1) rek(lo, mid-1, pi_lo, ind, br);
        else rek(lo, mid-1, pi_lo, pi_hi, br);
        rek(mid+1, hi, max(ind, pi_lo), pi_hi, br);
    }
}

void load() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<n; ++i) {
        for (int j=0; j<m; ++j) {
            char ch;
            scanf(" %c", &ch);
            if (ch=='.') mat[i][j]=-1;
            else mat[i][j]=ch-'0';
        }
    }
}

void solve() {
    memset(dp, -1, sizeof dp);
    for (int i=0; i<n; ++i) {
        for (int j=0; j<m; ++j) {
            if (!bio[i][j] && mat[i][j]!=-1) bfs(i, j);
        }
    }
    prec();
    int res=0;
    for (int i=0; i<m; ++i) {
        res=max(res, uk[i]);
        dp[i][0]=uk[i];
    }
    printf("%d\n", res);
    for (int i=1; i<m; ++i) {
        rek(0, m-1, 0, m-1, i);
        for (int j=0; j<m; ++j) {
            res=max(res, dp[j][i]);
        }
        printf("%d\n", res);
    }
}

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

Compilation message (stderr)

nafta.cpp: In function 'void load()':
nafta.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
nafta.cpp:116:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c", &ch);
             ~~~~~^~~~~~~~~~~~

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