Submission #743857

#	Time	Username	Problem	Language	Result	Execution time	Memory
743857		Seb	Nafta (COI15_nafta)	C++17	0 / 100	1 ms	1620 KiB

nafta

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define f first
#define s second

const ll MAXN = 2005;

ll dp[MAXN][MAXN],sz[MAXN][MAXN],val[MAXN][MAXN],izq[MAXN][MAXN],ans[MAXN];
pair <ll,ll> padre[MAXN][MAXN],nulo;
char ar[MAXN][MAXN];
vector <pair<ll,ll>> q[MAXN];
set <pair<ll,ll>> st;

pair <ll,ll> lider(pair<ll,ll> a) {
    if (padre[a.f][a.s] == nulo) {
        padre[a.f][a.s] = a;
        sz[a.f][a.s] = 1;
        izq[a.f][a.s] = a.s;
        if (ar[a.f][a.s]!='.') val[a.f][a.s] = ((ll)(ar[a.f][a.s])-48);
    }
    if (padre[a.f][a.s]==a) return a;
    padre[a.f][a.s] = lider(padre[a.f][a.s]);
    return padre[a.f][a.s];
}

void unir(pair <ll,ll> a, pair <ll,ll> b) {
    a = lider(a);
    b = lider(b);
    if (sz[a.f][a.s] < sz[b.f][b.s]) swap(a,b);
    padre[b.f][b.s] = a;
    sz[a.f][a.s] += sz[b.f][b.s];
    izq[a.f][a.s] = min(izq[a.f][a.s],izq[b.f][b.s]);
    val[a.f][a.s] += val[b.f][b.s];
    return;
}

void solve(ll lvl, ll ini, ll fin, ll k1, ll k2) {
    if (ini>fin) return;
    ll p=0,sum=0,K = (k1+k2)/2;
    if (!q[(ini+fin)/2].empty()) p = q[(ini+fin)/2].size()-1;
    for (int i=min(k2,(ini+fin)/2);i>=k1;i--) {
        while (p>=0 && i<q[(ini+fin)/2][p].f) {
            sum += q[(ini+fin)/2][p].s;
            p--;
        }
        if (dp[(ini+fin)/2][lvl] <= dp[i][lvl-1] + sum) {
            K = i;
            dp[(ini+fin)/2][lvl] = dp[i][lvl-1] + sum;
        }
    }
    ans[lvl] = max(ans[lvl],dp[(ini+fin)/2][lvl]);
    solve(lvl,ini,(ini+fin)/2-1,k1,K);
    solve(lvl,(ini+fin)/2+1,fin,K,k2);
    return;
}

int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
ll n,m,sum=0;
cin>>n>>m;
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) {
    cin>>ar[i][j];
    if (ar[i][j]!='.') {
        if (i>1 && ar[i-1][j]!='.') unir({i,j},{i-1,j});
        if (j>1 && ar[i][j-1]!='.') unir({i,j},{i,j-1});
    }
}
for (int j=1;j<=m;j++) {
    for (int i=1;i<=n;i++) if (st.find(lider({i,j}))==st.end()) {
        pair<ll,ll> aux = lider({i,j});
        q[j].push_back({izq[aux.f][aux.s],val[aux.f][aux.s]});
        st.insert(aux);
        sum += val[aux.f][aux.s];
    }
    dp[j][1] = sum;
    ans[1] = max(ans[1],sum);
    sort(q[j].begin(),q[j].end());
    sum = 0;
    st.clear();
}
cout<<ans[1]<<'\n';
for (int i=2;i<=m;i++) {
    solve(i,1,m,1,m);
    cout<<ans[i]<<'\n';
}
return 0;
}

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