oj.uz

Submission #1007319

# Submission time Handle Problem Language Result Execution time Memory
1007319 2024-06-24T15:41:14 Z VMaksimoski008 Nafta (COI15_nafta) C++17
34 / 100
 1000 ms 111556 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;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,bmi,bmi2,lzcnt,popcnt")


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 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 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 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 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 35 ms 5168 KB Output is correct
8 Correct 46 ms 4184 KB Output is correct
9 Correct 25 ms 5212 KB Output is correct
10 Correct 33 ms 4436 KB Output is correct
11 Correct 49 ms 3668 KB Output is correct
12 Correct 57 ms 3408 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 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 35 ms 5168 KB Output is correct
8 Correct 46 ms 4184 KB Output is correct
9 Correct 25 ms 5212 KB Output is correct
10 Correct 33 ms 4436 KB Output is correct
11 Correct 49 ms 3668 KB Output is correct
12 Correct 57 ms 3408 KB Output is correct
13 Execution timed out 1044 ms 111556 KB Time limit exceeded
14 Halted 0 ms 0 KB -