oj.uz

Submission #121970

# Submission time Handle Problem Language Result Execution time Memory
121970 2019-06-27T10:07:07 Z BartolM Nafta (COI15_nafta) C++17
100 / 100
 780 ms 79416 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16768 KB Output is correct
2 Correct 15 ms 16768 KB Output is correct
3 Correct 14 ms 16768 KB Output is correct
4 Correct 14 ms 16768 KB Output is correct
5 Correct 16 ms 16768 KB Output is correct
6 Correct 15 ms 16768 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16768 KB Output is correct
2 Correct 15 ms 16768 KB Output is correct
3 Correct 14 ms 16768 KB Output is correct
4 Correct 14 ms 16768 KB Output is correct
5 Correct 16 ms 16768 KB Output is correct
6 Correct 15 ms 16768 KB Output is correct
7 Correct 28 ms 20992 KB Output is correct
8 Correct 29 ms 20984 KB Output is correct
9 Correct 28 ms 20736 KB Output is correct
10 Correct 25 ms 20096 KB Output is correct
11 Correct 27 ms 19936 KB Output is correct
12 Correct 26 ms 19968 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16768 KB Output is correct
2 Correct 15 ms 16768 KB Output is correct
3 Correct 14 ms 16768 KB Output is correct
4 Correct 14 ms 16768 KB Output is correct
5 Correct 16 ms 16768 KB Output is correct
6 Correct 15 ms 16768 KB Output is correct
7 Correct 28 ms 20992 KB Output is correct
8 Correct 29 ms 20984 KB Output is correct
9 Correct 28 ms 20736 KB Output is correct
10 Correct 25 ms 20096 KB Output is correct
11 Correct 27 ms 19936 KB Output is correct
12 Correct 26 ms 19968 KB Output is correct
13 Correct 751 ms 79416 KB Output is correct
14 Correct 759 ms 72952 KB Output is correct
15 Correct 780 ms 66296 KB Output is correct
16 Correct 644 ms 68116 KB Output is correct
17 Correct 629 ms 61944 KB Output is correct
18 Correct 616 ms 61932 KB Output is correct