oj.uz

Submission #1039106

# Submission time Handle Problem Language Result Execution time Memory
1039106 2024-07-30T12:56:45 Z coin_ Nafta (COI15_nafta) C++14
100 / 100
 241 ms 146000 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;
void dnc(int l, int r, int optl, int optr){
    if (l > r) return;
    int mid = (l + r)/2;

    pair<int, int> best = {-1, -1};
    for (int k = optl; k <= min(mid, optr); k++){
        best = max(best, {cost[k][mid] + dp_pre[k], k});
    }

    int opt = best.second;
    dp_cur[mid] = best.first;
    dnc(l, mid-1, optl, opt);
    dnc(mid+1, r, opt, optr);
}

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;
        dnc(1, m, 1, m);
        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 28 ms 63312 KB Output is correct
2 Correct 28 ms 63316 KB Output is correct
3 Correct 27 ms 63324 KB Output is correct
4 Correct 27 ms 63328 KB Output is correct
5 Correct 28 ms 63320 KB Output is correct
6 Correct 27 ms 63312 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 63312 KB Output is correct
2 Correct 28 ms 63316 KB Output is correct
3 Correct 27 ms 63324 KB Output is correct
4 Correct 27 ms 63328 KB Output is correct
5 Correct 28 ms 63320 KB Output is correct
6 Correct 27 ms 63312 KB Output is correct
7 Correct 30 ms 63480 KB Output is correct
8 Correct 34 ms 63576 KB Output is correct
9 Correct 32 ms 65104 KB Output is correct
10 Correct 30 ms 63316 KB Output is correct
11 Correct 31 ms 63408 KB Output is correct
12 Correct 36 ms 63576 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 63312 KB Output is correct
2 Correct 28 ms 63316 KB Output is correct
3 Correct 27 ms 63324 KB Output is correct
4 Correct 27 ms 63328 KB Output is correct
5 Correct 28 ms 63320 KB Output is correct
6 Correct 27 ms 63312 KB Output is correct
7 Correct 30 ms 63480 KB Output is correct
8 Correct 34 ms 63576 KB Output is correct
9 Correct 32 ms 65104 KB Output is correct
10 Correct 30 ms 63316 KB Output is correct
11 Correct 31 ms 63408 KB Output is correct
12 Correct 36 ms 63576 KB Output is correct
13 Correct 179 ms 71332 KB Output is correct
14 Correct 214 ms 71252 KB Output is correct
15 Correct 241 ms 146000 KB Output is correct
16 Correct 169 ms 71252 KB Output is correct
17 Correct 171 ms 71328 KB Output is correct
18 Correct 156 ms 71248 KB Output is correct