oj.uz

Submission #844852

# Submission time Handle Problem Language Result Execution time Memory
844852 2023-09-06T04:43:56 Z Cookie Nafta (COI15_nafta) C++14
100 / 100
 231 ms 90704 KB 
#include<bits/stdc++.h>
#define ll long long
#define vt vector
#define pb push_back
#define pii pair<int, int>
#define sz(v) (int)v.size()
using namespace std;
const ll base = 107, mod = 1e9 + 7;
const int mxn = 2005, inf = 1e9, sq = 400;
const int X[4] = {1, -1, 0, 0};
const int Y[4] = {0, 0, 1, -1};
struct BIT{
    ll bit[mxn + 1];
    void upd(int p, ll v){
        while(p <= mxn){
            bit[p] += v; p += p & (-p);
        }
    }
    ll get(int p){
        ll ans = 0;
        while(p){
            ans += bit[p]; p -= p & (-p);
        }
        return(ans);
    }
    ll query(int l, int r){
        if(l > r)return(0);
        return(get(r) - get(l - 1));
    }
    int kth(ll x){
        ll sm = 0, id = 0;
        for(int i = 18; i >= 0; i--){
            if(id + (1 << i) <= mxn && sm + bit[id + (1 << i)] < x){
                id += (1 << i); sm += bit[id];
            }
        }
        return(id + 1);
    }
};
BIT bit;
 
int n, m;
int sm = 0, mn, mx;
bool vis[2005][2005];
char c[2005][2005];
int cost[2005][2005], dp[2005][2005];
bool inside(int nwx, int nwy){
    return(nwx >= 1 && nwx <= n && nwy >= 1 && nwy <= m);
}
void dfs(int x, int y){
    mn = min(mn, y); mx = max(mx, y);
    vis[x][y] = 1; sm += (c[x][y] - '0');
    for(int i = 0; i < 4; i++){
        int nwx = x + X[i], nwy = y + Y[i];
        if(inside(nwx, nwy) && c[nwx][nwy] != '.' && !vis[nwx][nwy]){
            dfs(nwx, nwy);
        }
    }
}
void solve(int id, int l, int r, int bestl, int bestr){
    if(l > r)return;
    int mid = (l + r) >> 1;
    int &mx = dp[id][mid], idd = -1;
    for(int i = bestl; i <= min(mid - 1, bestr); i++){
        int cand = dp[id - 1][i] + cost[mid][i];
        if(cand > mx){
            mx = cand; idd = i;
        }
    }
    
    solve(id, l, mid - 1, bestl, idd); solve(id, mid + 1, r, idd, bestr);
}
struct E{
    int l, r, v;
};
vt<E>events[mxn + 1];
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> c[i][j];
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(c[i][j] != '.' && !vis[i][j]){
                sm = 0; mn = mx = j;
                dfs(i, j);
               
                events[mn].pb({mn, mx, sm}); events[mx + 1].pb({mn, mx, -sm});
            }
        }
    }
    
    for(int i = 1; i <= m; i++){
        for(auto [l, r, v]: events[i]){
            bit.upd(l, v); bit.upd(r + 1, -v);
        }
        for(int j = i - 1; j >= 0; j--){
            cost[i][j] = bit.get(i) - bit.get(j);
        }
    }
    
    for(int i = 1; i <= m; i++){
        dp[1][i] = cost[i][0];
    }
    cout << *max_element(dp[1] + 1, dp[1] + m + 1) << "\n";
    for(int i = 2; i <= m; i++){
        solve(i, i, m, i - 1, m);
        cout << *max_element(dp[i] + 1, dp[i] + m + 1) << "\n";
    }
    
}

Compilation message

nafta.cpp: In function 'int main()':
nafta.cpp:97:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   97 |         for(auto [l, r, v]: events[i]){
      |                  ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 2 ms 4952 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 2 ms 4952 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 6 ms 9048 KB Output is correct
8 Correct 6 ms 8792 KB Output is correct
9 Correct 7 ms 9820 KB Output is correct
10 Correct 6 ms 8796 KB Output is correct
11 Correct 5 ms 8792 KB Output is correct
12 Correct 4 ms 8536 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 2 ms 4952 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 6 ms 9048 KB Output is correct
8 Correct 6 ms 8792 KB Output is correct
9 Correct 7 ms 9820 KB Output is correct
10 Correct 6 ms 8796 KB Output is correct
11 Correct 5 ms 8792 KB Output is correct
12 Correct 4 ms 8536 KB Output is correct
13 Correct 167 ms 62316 KB Output is correct
14 Correct 193 ms 53840 KB Output is correct
15 Correct 231 ms 90704 KB Output is correct
16 Correct 131 ms 51288 KB Output is correct
17 Correct 124 ms 42836 KB Output is correct
18 Correct 120 ms 42616 KB Output is correct