oj.uz

Submission #121959

# Submission time Handle Problem Language Result Execution time Memory
121959 2019-06-27T09:40:34 Z BartolM Nafta (COI15_nafta) C++17
0 / 100
 3 ms 896 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=305;

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=lower_bound(R[j].begin(), R[j].end(), mp(i, -1))-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]);
        }
    }
}

int rek(int pos, int br) {
    if (br==0) return 0;

    int &ret=dp[pos][br];
    if (ret!=-1) return ret;
    ret=0;
    for (int j=pos+1; j<m; ++j) {
        ret=max(ret, rek(j, br-1)+val[pos][j]);
    }
    return ret;
}

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();
    for (int i=0; i<m; ++i) {
        int res=0;
        for (int j=0; j<m; ++j) {
            res=max(res, rek(j ,i)+uk[j]);
        }
        printf("%d\n", res);
    }
}

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

Compilation message

nafta.cpp: In function 'void load()':
nafta.cpp:102: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:106:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c", &ch);
             ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -