Submission #364639

#	Time	Username	Problem	Language	Result	Execution time	Memory
364639		Falseee	Nafta (COI15_nafta)	C++17	34 / 100	1056 ms	50228 KiB

nafta

#include <bits/stdc++.h>
using namespace std;


#define all(a) a.begin(),a.end()
#define REP(i,n)      for(int i=0;i<(n);++i)

const int MAXN = 2001;
char g[MAXN][MAXN];
bool vis[MAXN][MAXN]= {false};
struct item{
    int l = INT_MAX;
    int r, value;
    item(){
        l = INT_MAX;
        r = INT_MIN;
        value = 0;
    }
    bool operator < (item & other){
        return l < other.l;
    }
};
struct event{
    bool start;
    int val, pos, id;
    bool operator < (event & other){
        return pos < other.pos;
    }
};

int ids[MAXN][MAXN];

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int cost[MAXN][MAXN];
int n, m;
int C[MAXN][MAXN];
int before_dp[MAXN];
int current_dp[MAXN];
bool valid(int i, int j){
    return i>=0 && j >= 0 && i < n && j < m;
}
void flood(int i, int j){
    vis[i][j]=1;
    REP(pos, 4){
        int ci = dx[pos]+i;
        int cj = dy[pos]+j;
        if(valid(ci, cj) && !vis[ci][cj] && g[ci][cj] != '.'){
            ids[ci][cj]=ids[i][j];
            flood(ci, cj);

        }

    }
}
int gres = 0;

void solve(int l, int r, int optl, int optr){

    if(l > r)
        return;
    int mid = (l+r) /2;
    pair<int, int> best = {-1, -1};
    for(int k = optl ; k <= min(mid, optr); ++k){
        best = max(best, {before_dp[k]+C[k][mid], k});
    }
    current_dp[mid]=best.first;
    gres=max(gres, best.first);
    solve(l, mid-1, optl, best.second);
    solve(mid+1, r, best.second, optr);


}
int main(){
    ios_base::sync_with_stdio();
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    REP(i, n){
        REP(j, m){
            cin >> g[i][j];
        }
    }
    int t_id = 1;
    REP(i, n){
        REP(j, m){
            if(g[i][j]!= '.' && !vis[i][j]){
                ids[i][j] = t_id;
                vis[i][j]=1;
                ++t_id;
                flood(i,j);
            }
        }
    }

    --t_id;
    item ar[t_id];
    vector<event> events;
    REP(i, n){
        REP(j, m){
            if(ids[i][j])
            {
                ar[ids[i][j]-1].l = min(ar[ids[i][j]-1].l, j);
                ar[ids[i][j]-1].r = max(ar[ids[i][j]-1].r, j);
                ar[ids[i][j]-1].value+=g[i][j]-'0';
            }
        }
    }
    REP(i, t_id){
        events.push_back({1, ar[i].value, ar[i].l, i});
        events.push_back({0, ar[i].value, ar[i].r+1, i});
    }
    const int sz = events.size();
    sort(all(events));
    int s_point = 0;
    bool used[t_id];
         memset(used, 0, sizeof(used));
    for(int i = 0; i <= m; ++i){
        while(s_point < sz && events[s_point].pos < i ){
            used[events[s_point].id]=1;
            ++s_point;
        }
        int cur = s_point;
        int res = 0;
        for(int j = 0; j <= m; ++j){
            while(cur < sz && events[cur].pos < j){
                if(events[cur].start ){
                    res+=events[cur].val;
                }else if(!used[events[cur].id]) res-=events[cur].val;
                ++cur;
            }

            C[i][j]=res;


        }
    }
    memset(current_dp, 0, sizeof(current_dp));
    memset(before_dp, 0, sizeof(before_dp));

    for(int i = 0; i <m ; ++i){
        solve(i, m, i, m);
        swap(current_dp, before_dp);
        cout << gres << "\n";
    }



}

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 0 / 66