oj.uz

Submission #1050871

# Submission time Handle Problem Language Result Execution time Memory
1050871 2024-08-09T15:56:26 Z coin_ Nafta (COI15_nafta) C++14
34 / 100
 1000 ms 71248 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
 
const int maxcol = 2003;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1, 1};
vector<vector<int>> id(maxcol, vector<int>(maxcol, 0)), cost(maxcol, vector<int>(maxcol, 0));
 
void calculatecostfunction(int col){
    for (int end = 1; end <= col; end++){
        for (int start = end; start >= 0; start--){
            cost[start][end] = cost[start+1][end] + id[start+1][end];
        }
    }
}
 
int l, r, totalcost = 0;
void dfs(int x, int y, vector<vector<char>> &board, int n, int m){
    totalcost += board[y][x] - '0';
    board[y][x] = '.';
    l = min(l, x);
    r = max(r, x);
    for (int i = 0; i < 4; i++){
        int tx = x + dx[i], ty = y + dy[i];
        if (tx <= 0 || ty <= 0 || tx > m || ty > n) continue;
        if (board[ty][tx] != '.'){
            dfs(tx, ty, board, n, m);
        }
    }
}
 
vector<int> dp_pre, dp_cur;

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    vector<vector<char>> board(n+1, vector<char>(m+1));
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> board[i][j];
        }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (board[i][j] != '.'){
                l = m + 1, r = 0, totalcost = 0;
                dfs(j, i, board, n, m);
                for (int ptr = l; ptr <= r; ptr++){
                    id[l][ptr] += totalcost;
                }
            }
        }
    }
    calculatecostfunction(m);
    
    dp_cur.assign(m+1, 0);
    dp_pre.assign(m+1, 0);
    for (int i = 1; i <= m; i++){
        dp_cur[i] = cost[0][i];
    }
    int mx = 0;
    for (int i = 1; i <= m; i++){
        mx = max(mx, dp_cur[i]);
    }
    cout << mx << endl;
    for (int i = 2; i <= m; i++){
        dp_pre = dp_cur;
        dp_cur.assign(m+1, 0);
        for (int j = 1; j <= m; j++){
            for (int k = 1; k <= j; k++){
                dp_cur[j] = max(dp_cur[j], cost[k][j] + dp_pre[k]);
            }
        }
        mx = 0;
        for (int j = 1; j <= m; j++){
            mx = max(mx, dp_cur[j]);
        }
        cout << mx << endl;
    }
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 63312 KB Output is correct
2 Correct 23 ms 63312 KB Output is correct
3 Correct 23 ms 63312 KB Output is correct
4 Correct 23 ms 63324 KB Output is correct
5 Correct 22 ms 63204 KB Output is correct
6 Correct 25 ms 63324 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 63312 KB Output is correct
2 Correct 23 ms 63312 KB Output is correct
3 Correct 23 ms 63312 KB Output is correct
4 Correct 23 ms 63324 KB Output is correct
5 Correct 22 ms 63204 KB Output is correct
6 Correct 25 ms 63324 KB Output is correct
7 Correct 38 ms 63412 KB Output is correct
8 Correct 37 ms 63580 KB Output is correct
9 Correct 39 ms 65044 KB Output is correct
10 Correct 42 ms 63576 KB Output is correct
11 Correct 39 ms 63572 KB Output is correct
12 Correct 39 ms 63568 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 63312 KB Output is correct
2 Correct 23 ms 63312 KB Output is correct
3 Correct 23 ms 63312 KB Output is correct
4 Correct 23 ms 63324 KB Output is correct
5 Correct 22 ms 63204 KB Output is correct
6 Correct 25 ms 63324 KB Output is correct
7 Correct 38 ms 63412 KB Output is correct
8 Correct 37 ms 63580 KB Output is correct
9 Correct 39 ms 65044 KB Output is correct
10 Correct 42 ms 63576 KB Output is correct
11 Correct 39 ms 63572 KB Output is correct
12 Correct 39 ms 63568 KB Output is correct
13 Execution timed out 1026 ms 71248 KB Time limit exceeded
14 Halted 0 ms 0 KB -