oj.uz

Submission #1007317

# Submission time Handle Problem Language Result Execution time Memory
1007317 2024-06-24T15:40:44 Z VMaksimoski008 Nafta (COI15_nafta) C++17
34 / 100
 1000 ms 112412 KB 
#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using Comp = array<ll, 3>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;

struct SegTree {
    int n;
    vector<vector<pii> > tree, v;
    vector<vector<int> > suf;

    void init(vector<vector<pii> > &_c) {
        v = _c;
        n = v.size() - 1;
        suf.resize(4*n+10);
        tree.resize(4*n+10);
        build(1, 1, n);
    }

    void build(int u, int tl, int tr) {
        if(tl == tr) {
            tree[u] = v[tl];
            if(!tree[u].empty()) {
                suf[u].resize(tree[u].size());
                suf[u].back() = tree[u].back().second;
                for(int i=suf[u].size()-2; i>=0; i--) suf[u][i] = suf[u][i+1] + tree[u][i].second;
            }
        } else {
            int tm = (tl + tr) / 2;
            build(2*u, tl, tm);
            build(2*u+1, tm+1, tr);
            merge(all(tree[2*u]), all(tree[2*u+1]), back_inserter(tree[u]));
            if(!tree[u].empty()) {
                suf[u].resize(tree[u].size());
                suf[u].back() = tree[u].back().second;
                for(int i=suf[u].size()-2; i>=0; i--) suf[u][i] = suf[u][i+1] + tree[u][i].second;
            }
        }
    }

    int query(int u, int tl, int tr, int l, int r) {
        if(tl > tr || l > tr || tl > r) return 0;
        if(l <= tl && tr <= r) {
            if(tree[u].empty() || tree[u].back().first < r) return 0;
            auto p = lower_bound(tree[u].begin(), tree[u].end(), pii{ r, 0 }) - tree[u].begin();
            return suf[u][(int)p];
        }

        int tm = (tl + tr) / 2;
        return query(2*u, tl, tm, l, r) + query(2*u+1, tm+1, tr, l, r);
    }

    int query(int l, int r) { return query(1, 1, n, l, r); }
} tree;

int dr[8] = {0, -1, 0, 1, 1, 1, -1, -1};
int dc[8] = {-1, 0, 1, 0, 1, -1, 1, -1};
char mat[2005][2005];
bool vis[2005][2005];
int L=1e9, R=-1, sum=0, n, m;

void dfs(int r, int c) {
    vis[r][c] = 1;
    L = min(L, c); R = max(R, c);
    sum += (mat[r][c] - '0');

    for(int i=0; i<4; i++) {
        int newR = r + dr[i];
        int newC = c + dc[i];
        if(newR < 0 || newR >= n || newC < 0 || newC >= m) continue;
        if(vis[newR][newC] || mat[newR][newC] == '.') continue;
        dfs(newR, newC);
    }
}

int dp[2005][2005];

void f(int l, int r, int tl, int tr, int j) {
    if(l > r) return ;
    int tm = (l + r) / 2, p = tl;

    // if(j == 2) cout << l << " " << r << " " << tl << " " << tr << '\n';
    for(int i=tl; i<=min(tm, tr); i++) {
        // if(j == 2) cout << i << " " << tm << ": " << tree.query(i, tm) << '\n';
        ll v = dp[i-1][j-1] + tree.query(i, tm);
        if(v > dp[tm][j]) {
            dp[tm][j] = v;
            p = i;
        }
    }

    f(l, tm-1, tl, p, j);
    f(tm+1, r, p, tr, j);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    cin >> n >> m;
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++) cin >> mat[i][j];

    vector<vector<pii> > vec(m+1);
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            if(vis[i][j] || mat[i][j] == '.') continue;
            L=1e9, R=-1, sum=0;
            dfs(i, j);
            vec[L+1].push_back({ R+1, sum });
        }
    }
    
    for(int i=1; i<=m; i++) sort(vec[i].begin(), vec[i].end());
    tree.init(vec);

    for(int i=1; i<=m; i++) {
        f(1, m, 1, m, i);
        int mx = 0;
        for(int j=1; j<=m; j++) mx = max(mx, dp[j][i]);
        cout << mx << '\n';
    }
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 33 ms 5204 KB Output is correct
8 Correct 34 ms 4184 KB Output is correct
9 Correct 26 ms 5212 KB Output is correct
10 Correct 30 ms 4436 KB Output is correct
11 Correct 62 ms 3640 KB Output is correct
12 Correct 73 ms 3284 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 33 ms 5204 KB Output is correct
8 Correct 34 ms 4184 KB Output is correct
9 Correct 26 ms 5212 KB Output is correct
10 Correct 30 ms 4436 KB Output is correct
11 Correct 62 ms 3640 KB Output is correct
12 Correct 73 ms 3284 KB Output is correct
13 Execution timed out 1050 ms 112412 KB Time limit exceeded
14 Halted 0 ms 0 KB -