oj.uz

Submission #1007315

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

    SegTree(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); }
};

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);
    }
}

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 });
        }
    }

    int dp[m+1][m+1];
    memset(dp, 0, sizeof(dp));
    for(int i=1; i<=m; i++) sort(vec[i].begin(), vec[i].end());
    SegTree tree(vec);

    for(int i=1; i<=m; i++) {
        for(int j=1; j<=i; j++) {
            for(int k=0; k<i; k++) {
                dp[i][j] = max(dp[i][j], dp[k][j-1] + tree.query(k+1, i));
            }
        }
    }
    
    for(int i=1; i<=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 600 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 732 KB Output is correct
5 Correct 2 ms 704 KB Output is correct
6 Correct 2 ms 604 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 732 KB Output is correct
5 Correct 2 ms 704 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 505 ms 3932 KB Output is correct
8 Correct 615 ms 3116 KB Output is correct
9 Correct 419 ms 3676 KB Output is correct
10 Correct 555 ms 3160 KB Output is correct
11 Correct 596 ms 2516 KB Output is correct
12 Correct 658 ms 2284 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 732 KB Output is correct
5 Correct 2 ms 704 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 505 ms 3932 KB Output is correct
8 Correct 615 ms 3116 KB Output is correct
9 Correct 419 ms 3676 KB Output is correct
10 Correct 555 ms 3160 KB Output is correct
11 Correct 596 ms 2516 KB Output is correct
12 Correct 658 ms 2284 KB Output is correct
13 Execution timed out 1046 ms 116196 KB Time limit exceeded
14 Halted 0 ms 0 KB -