oj.uz

Submission #704829

# Submission time Handle Problem Language Result Execution time Memory
704829 2023-03-03T04:50:00 Z kelfert Nafta (COI15_nafta) C++17
34 / 100
 1000 ms 53252 KB 
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

#define all(x) (x).begin(), (x).end()
typedef long long ll;

const int INF = 2e9;
const int N = 2001;

int cost[N][N], used[N][N], a[N][N], dp[N][N], cnt2[N];
int opt, mid; 

void divide(int j, int l, int r, int ql, int qr) {
    if (l >= r) return;
    mid = (l + r) / 2;
    for (int i = ql; i < min(mid, qr); i++) {
        if (dp[j][mid] < dp[j - 1][i] + cost[i][mid]) {
            dp[j][mid] = dp[j - 1][i] + cost[i][mid];
            opt = i;
        }
    }
    divide(j, l, mid, ql, opt + 1);
    divide(j, mid + 1, r, opt, qr);
}

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

void dfs(int vx, int vy, int &sum, int &l, int &r) {
    used[vx][vy] = 1;
    sum += a[vx][vy];
    l = min(l, vy);
    r = max(r, vy);
    for (int k = 0; k < 4; k++) {
        int x = vx + dx[k], y = vy + dy[k];
        if (!used[x][y] && a[x][y] != -1) {
            dfs(x, y, sum, l, r);
        }
    }
} 

struct Event {
    int x, id, tp, sum;
    Event(int x, int id, int tp, int sum) : x(x), id(id), tp(tp), sum(sum) {}
};

bool comp(Event a, Event b) {
    return a.x < b.x;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m; cin >> n >> m;
    for (int i = 0; i <= n + 1; i++)
        for (int j = 0; j <= m + 1; j++)
            a[i][j] = -1;
    string s;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        for (int j = 0; j < m; j++)
            if (s[j] != '.') a[i][j + 1] = (s[j] - '0');
    }
    vector<int> seg;
    vector<Event> events;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!used[i][j] && a[i][j] != -1) {
                int sum = 0, l = j, r = j;
                dfs(i, j, sum, l, r);
                seg.push_back(l);
                events.push_back(Event(l, seg.size() - 1, 1, sum));
                events.push_back(Event(r, seg.size() - 1, -1, sum));
            }
        }
    }
    sort(all(events), comp);
    for (auto x : events) {
        if (x.tp == 1) cnt2[x.x] += x.sum;
    }
    int first = 0, sz = events.size();
    for (int l = 0; l <= m; l++) {
        while (first < sz && events[first].x <= l) first++;
        int i = first, sum = 0;
        for (int r = l + 1; r <= m; r++) {
            while (i < sz && events[i].x < r) {
                if (events[i].tp == 1) sum += events[i].sum;
                else if (seg[events[i].id] > l) sum -= events[i].sum;
                i++;    
            }
            cost[l][r] = sum + cnt2[r];
        }
    }
    int ans = 0;
    for (int j = 1; j <= m; j++) {
        divide(j, 0, m + 1, 0, m + 1);
        ans = 0;
        for (int i = 1; i <= m; i++) ans = max(ans, dp[j][i]);
        cout << ans << "\n";
    }
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1188 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1188 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 21 ms 6844 KB Output is correct
8 Correct 15 ms 6684 KB Output is correct
9 Correct 10 ms 8404 KB Output is correct
10 Correct 14 ms 6060 KB Output is correct
11 Correct 9 ms 5716 KB Output is correct
12 Correct 7 ms 5592 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1188 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 21 ms 6844 KB Output is correct
8 Correct 15 ms 6684 KB Output is correct
9 Correct 10 ms 8404 KB Output is correct
10 Correct 14 ms 6060 KB Output is correct
11 Correct 9 ms 5716 KB Output is correct
12 Correct 7 ms 5592 KB Output is correct
13 Execution timed out 1087 ms 53252 KB Time limit exceeded
14 Halted 0 ms 0 KB -