oj.uz

Submission #960573

# Submission time Handle Problem Language Result Execution time Memory
960573 2024-04-10T15:59:37 Z Niosakaru Nafta (COI15_nafta) C++17
100 / 100
 871 ms 259104 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] , opt[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){
            int Le = max(opt[i][k-1],opt[i-1][k]) , Ri = i;
            if (k == 1) Le = Ri = 1;
            rep(j,Le,Ri){
                s = dp[j - 1][k - 1] + e[j][i];
                if (s > dp[i][k]){
                    dp[i][k] = s;
                    opt[i][k] = j;
                }
            }
            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 5 ms 37976 KB Output is correct
2 Correct 6 ms 37980 KB Output is correct
3 Correct 7 ms 37980 KB Output is correct
4 Correct 7 ms 37724 KB Output is correct
5 Correct 6 ms 37724 KB Output is correct
6 Correct 6 ms 37724 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 37976 KB Output is correct
2 Correct 6 ms 37980 KB Output is correct
3 Correct 7 ms 37980 KB Output is correct
4 Correct 7 ms 37724 KB Output is correct
5 Correct 6 ms 37724 KB Output is correct
6 Correct 6 ms 37724 KB Output is correct
7 Correct 12 ms 49756 KB Output is correct
8 Correct 13 ms 49756 KB Output is correct
9 Correct 14 ms 51288 KB Output is correct
10 Correct 11 ms 48780 KB Output is correct
11 Correct 12 ms 48732 KB Output is correct
12 Correct 14 ms 46684 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 37976 KB Output is correct
2 Correct 6 ms 37980 KB Output is correct
3 Correct 7 ms 37980 KB Output is correct
4 Correct 7 ms 37724 KB Output is correct
5 Correct 6 ms 37724 KB Output is correct
6 Correct 6 ms 37724 KB Output is correct
7 Correct 12 ms 49756 KB Output is correct
8 Correct 13 ms 49756 KB Output is correct
9 Correct 14 ms 51288 KB Output is correct
10 Correct 11 ms 48780 KB Output is correct
11 Correct 12 ms 48732 KB Output is correct
12 Correct 14 ms 46684 KB Output is correct
13 Correct 321 ms 180232 KB Output is correct
14 Correct 358 ms 185940 KB Output is correct
15 Correct 430 ms 259104 KB Output is correct
16 Correct 307 ms 176460 KB Output is correct
17 Correct 666 ms 176724 KB Output is correct
18 Correct 871 ms 175832 KB Output is correct