Submission #844851

#	Time	Username	Problem	Language	Result	Execution time	Memory
844851		Cookie	Nafta (COI15_nafta)	C++14	0 / 100	1 ms	4952 KiB

nafta

#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(r - 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 (stderr)

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: 0 / 11
• Subtask 2: 0 / 23
• Subtask 3: 0 / 66