Submission #931180

#	Time	Username	Problem	Language	Result	Execution time	Memory
931180		dosts	Nafta (COI15_nafta)	C++17	34 / 100	1110 ms	519636 KiB

nafta

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define sp << " " << 
#define int long long
#define ff first
#define ss second
#define vi vector<int>
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
template<typename T1, typename T2> bool MIN(T1 &a, T2 b){return a > b ? a = b, true : false;}
template<typename T1, typename T2> bool MAX(T1 &a, T2 b){return a < b ? a = b, true : false;}
 
const int  N = 2e3+2,inf = 2e18;
 
pii dad[N][N];
int sm[N][N];
pii find(int x,int y) {
    if (pii{x,y} == dad[x][y]) return dad[x][y];
    return dad[x][y] = find(dad[x][y].first,dad[x][y].second);
}
void unite(int x1,int y1,int x2,int y2) {
    sm[find(x2,y2).first][find(x2,y2).second]+=sm[find(x1,y1).first][find(x1,y1).second];
    dad[find(x1,y1).first][find(x1,y1).second] = find(x2,y2);
}
 
 
int common[N][N];
int util[N];
int sag[N][N];
vector<pii> edges[N][N];
int vis[N][N];

void dfs(int x,int y,int z) {
    if (vis[x][y]) return;
    //cout << x sp y sp z << '\n';
    vis[x][y] = 1;
    sag[x][y] = z;
    for (auto it : edges[x][y]) dfs(it.first,it.second,z);
}

vi dp_prev(N,0),dp(N,0);
 
void dnc(int optl,int optr,int l,int r) {
    if (l > r) return; 
    int m = (l+r) >> 1;
    int opt = optl,best = 0;
    for (int i=optl;i<=min(optr,m-1);i++) {
        if (dp_prev[i]+util[m]-common[i][m] > best) {
            best = dp_prev[i]+util[m]-common[i][m];
            opt = i;
        };
    }
    dp[m] = best;
    dnc(optl,opt,l,m-1);
    dnc(opt,optr,m+1,r);
}
 
 
void solve() { 
    int n,m;
    cin >> n >> m;
    for (int i=1;i<=m;i++) for (int j=1;j<=m;j++) common[i][j] = 0;
    for (int i=1;i<=m;i++) util[i] = 0;
    vector<vi> a(n+1,vi(m+1));
    int dot = '.'-'0';
    for (int i=1;i<=n;i++) {
        string s;
        cin >> s;
        for (int j=1;j<=m;j++) {
            if (s[j-1]>='0' && s[j-1] <= '9') {
                a[i][j] = s[j-1]-'0';
            }
            else a[i][j] = -2;
        }
    }
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) dad[i][j] = {i,j},sm[i][j] = max(0ll,a[i][j]);
    vi dx{1,0,-1,0},dy{0,1,0,-1};
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            if(a[i][j] == dot) continue;
            for (int d = 0;d<4;d++) {
                int gx = i+dx[d],gy = j+dy[d];
                if (gx < 1 || gx > n || gy < 1 || gy > m) continue;
                if (a[gx][gy] == dot) continue;
                edges[i][j].push_back({gx,gy});
                edges[gx][gy].push_back({i,j});
                if (find(i,j) == find(gx,gy)) continue;
                unite(i,j,gx,gy);
            }
        }
    }

    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) vis[i][j] = 0;
    for (int i=m;i>=1;i--){
        for (int j = 1;j<=n;j++) {
            dfs(j,i,i);
        }
    }
    int got[n+1][m+1];
    memset(got,0,sizeof got);
    for (int i=1;i<=m;i++) {
        vector<pair<pii,int>> pushed;
        for (int r=1;r<=n;r++) {
            if (a[r][i] == dot) continue;
            auto[x,y] = find(r,i);
            pushed.push_back({{x,y},r});
        }
        for (auto itt : pushed) {
            pii it = itt.first;
            int r = itt.second;
            if (got[it.first][it.second]) continue;
            got[it.first][it.second] = 1;
            util[i]+=sm[it.first][it.second];
            common[i][i]+=sm[it.first][it.second];
            common[i][sag[r][i]+1]-=sm[it.first][it.second];
        }
        for (auto it : pushed) if (got[it.ff.first][it.ff.second]) got[it.ff.first][it.ff.second] = 0;
    }
    for (int i=1;i<=m;i++) {
        for (int j=i+1;j<=m;j++) common[i][j]+=common[i][j-1];
    }    
    for (int i=1;i<=m;i++) {
        for (int j=1;j<i;j++) common[i][j]= common[j][i];
    }
    for (int i=1;i<=m;i++) dp_prev[i] = util[i];
    cout << *max_element(dp_prev.begin()+1,dp_prev.end()) << '\n';
    for (int i=2;i<=m;i++) {
        dnc(0,m,1,m);
        cout << *max_element(dp.begin(),dp.end());
        if(i != m) cout << endl;
        dp_prev = dp;
        for (int j=1;j<=m;j++) dp[j] = 0;
    }
}
                 
                             
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
 
    int t = 1;
    //cin >> t; 
	while (t --> 0) solve();
}

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