Submission #931194

#	Time	Username	Problem	Language	Result	Execution time	Memory
931194		dosts	Nafta (COI15_nafta)	C++17	100 / 100	973 ms	335720 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 = 2e9;
 
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) {
    pii f1 = find(x1,y1);
    pii f2 = find(x2,y2);
    if (f1 == f2) return;
    sm[f2.first][f2.second]+=sm[f1.first][f1.second];
    dad[f1.first][f1.second] = f2;
}
 
 
int common[N][N];
int util[N];
vector<pii> edges[N][N];
int vis[N][N];
 
void dfs(int x,int y,int z) {
    if (vis[x][y]) return;
    vis[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(0,a[i][j]);
    vi dx{1,0},dy{0,1};
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            vis[i][j] = 0;
            if(a[i][j] == dot) continue;
            for (int d = 0;d<2;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});
                unite(i,j,gx,gy);
            }
        }
    }
    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][vis[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++) 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 << '\n';
        dp_prev = dp;
    }
}
                 
                             
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: 66 / 66