oj.uz

Submission #960545

# Submission time Handle Problem Language Result Execution time Memory
960545 2024-04-10T15:40:59 Z Niosakaru Nafta (COI15_nafta) C++17
34 / 100
 1000 ms 138748 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i,l,r) for (int i = l ; i <= r ; i ++)
#define N 2020

const int mod = 1e9 + 7 , base = 311;

int n , m , s , r , w[N][N] , e[N][N] , a[N][N] , vs[N][N] , rs[N] , dp[N][N] , dx[] = {0,0,-1,1} , dy[] = {1,-1,0,0};

int bfs(int u,int v){
    r = max(r,v); vs[u][v] = 1;
    int sum = a[u][v];
    rep(i,0,3){
        int x = u + dx[i] , y = v + dy[i];
        if (1 > x || 1 > y || n < x || m < y || vs[x][y] || a[x][y] == -1) continue;
        sum += bfs(x,y);
    }
    return sum;
}

signed main(){
    cin.tie(NULL)->sync_with_stdio(NULL);

    cin >> n >> m;
    memset(a , -1 , sizeof a);
    rep(i,1,n) rep(j,1,m)
    {
        char c; cin >> c;
        if (c == '.') continue;
        a[i][j] = c - '0';
    }

    rep(j,1,m) rep(i,1,n)
    {
        if (vs[i][j] || a[i][j] == -1) continue;
        r = j , s = bfs(i,j);
        w[j][r] += s;
    }

    for (int i = m ; i ; i --){
        s = 0;
        for (int j = m ; j >= i ; j --){
            s += w[i][j];
            e[i][j] = e[i + 1][j] + s;
        }
    }

    rep(k,1,m){
        rep(i,1,m) rep(j,0,i-1){
            dp[i][k] = max(dp[i][k] , dp[j][k - 1] + e[j + 1][i]);
            rs[k] = max(rs[k] , dp[i][k]);
        }
    }

    rep(i,1,m)
        cout << rs[i] << '\n';
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 35676 KB Output is correct
2 Correct 6 ms 35676 KB Output is correct
3 Correct 5 ms 35676 KB Output is correct
4 Correct 6 ms 35584 KB Output is correct
5 Correct 5 ms 35676 KB Output is correct
6 Correct 5 ms 35676 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 35676 KB Output is correct
2 Correct 6 ms 35676 KB Output is correct
3 Correct 5 ms 35676 KB Output is correct
4 Correct 6 ms 35584 KB Output is correct
5 Correct 5 ms 35676 KB Output is correct
6 Correct 5 ms 35676 KB Output is correct
7 Correct 31 ms 45908 KB Output is correct
8 Correct 32 ms 45912 KB Output is correct
9 Correct 32 ms 47548 KB Output is correct
10 Correct 32 ms 44904 KB Output is correct
11 Correct 28 ms 44888 KB Output is correct
12 Correct 32 ms 44968 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 35676 KB Output is correct
2 Correct 6 ms 35676 KB Output is correct
3 Correct 5 ms 35676 KB Output is correct
4 Correct 6 ms 35584 KB Output is correct
5 Correct 5 ms 35676 KB Output is correct
6 Correct 5 ms 35676 KB Output is correct
7 Correct 31 ms 45908 KB Output is correct
8 Correct 32 ms 45912 KB Output is correct
9 Correct 32 ms 47548 KB Output is correct
10 Correct 32 ms 44904 KB Output is correct
11 Correct 28 ms 44888 KB Output is correct
12 Correct 32 ms 44968 KB Output is correct
13 Execution timed out 1029 ms 138748 KB Time limit exceeded
14 Halted 0 ms 0 KB -