oj.uz

Submission #121960

# Submission time Handle Problem Language Result Execution time Memory
121960 2019-06-27T09:42:12 Z BartolM Nafta (COI15_nafta) C++17
34 / 100
 63 ms 2176 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=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]);
        }
    }
}

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 896 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 3 ms 896 KB Output is correct
5 Correct 3 ms 940 KB Output is correct
6 Correct 3 ms 896 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 896 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 3 ms 896 KB Output is correct
5 Correct 3 ms 940 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 62 ms 2176 KB Output is correct
8 Correct 63 ms 2104 KB Output is correct
9 Correct 61 ms 2012 KB Output is correct
10 Correct 59 ms 2048 KB Output is correct
11 Correct 58 ms 2040 KB Output is correct
12 Correct 59 ms 1840 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 896 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 3 ms 896 KB Output is correct
5 Correct 3 ms 940 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 62 ms 2176 KB Output is correct
8 Correct 63 ms 2104 KB Output is correct
9 Correct 61 ms 2012 KB Output is correct
10 Correct 59 ms 2048 KB Output is correct
11 Correct 58 ms 2040 KB Output is correct
12 Correct 59 ms 1840 KB Output is correct
13 Incorrect 33 ms 1848 KB Output isn't correct
14 Halted 0 ms 0 KB -