Submission #1089091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089091		nghiaaa	Nafta (COI15_nafta)	C++14	100 / 100	204 ms	129784 KiB

nafta

#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define ll long long
#define db double
#define ii pair<int,int>
#define f first
#define s second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define all(v) v.begin(),v.end()
#define BIT(i) ((ll)1<<(i))
#define debug(x) for (auto p: x) cout<<p<<' ';cout<<endl
#define forw(i,j,z) for(int i=(int)j;i<=(int)z;i++)
#define ford(i,j,z) for (int i=(int)j;i>=(int)z;i--)
#define sz(a) (int)a.size()
#define len(a) (int)a.length()
const int N = 2000 + 2;
int a[N][N];
int n, m, cost[N][N];
int dp[N][N];
struct DSU{
    int root, size, l, r, cost;
};
DSU dsu[N * N];
int h[N];
bool mark[N * N];
int getid(int x, int y)
{
    return (x - 1) * m + y;
}
int findset(int u)
{
    return u == dsu[u].root ? u : dsu[u].root = findset(dsu[u].root);
}
void Union(int u, int v)
{
    u = findset(u), v = findset(v);
    if (u == v) return ;
    if (dsu[u].size < dsu[v].size) swap(u, v);
    dsu[u].size += dsu[v].size;
    dsu[v].root = u;
    dsu[u].l = min(dsu[u].l, dsu[v].l);
    dsu[u].r = max(dsu[u].r, dsu[v].r);
    dsu[u].cost += dsu[v].cost;
}
void DAC(int l, int r, int L, int R, int c)
{
    int mid = (l + r) >> 1;
    int costbest = -1, savebest = -1;
    forw(i, L, min(mid, R))
    {
        int costi = cost[i][mid] + dp[i - 1][c - 1];
        if (costi > costbest)
            costbest = costi, savebest = i;
    }
    dp[mid][c] = costbest;
    if (l == r)
        return ;
    DAC(l, mid, L, savebest, c);
    DAC(mid + 1, r, savebest, R, c);
}
void solve()
{
    cin >> n >> m;
    forw(i, 1, n) forw(j, 1, m)
    {
        char val; cin >> val;
        a[i][j] = (val == '.' ? -1 : val - '0');
    }
    forw(i, 1, n) forw(j, 1, m)
    {
        if (a[i][j] < 0) continue;
        int r1 = getid(i, j);
        dsu[r1] = {r1, 1, j, j, a[i][j]};
        if (i > 1 && a[i - 1][j] >= 0)
            Union(r1, getid(i - 1, j));
        if (j > 1 && a[i][j - 1] >= 0)
            Union(r1, getid(i, j - 1));
    }
    forw(i, 1, n) forw(j, 1, m)
        if (a[i][j] >= 0 && !mark[findset(getid(i, j))])
        {
            int r1 = findset(getid(i, j));
            mark[r1] = 1;
            forw(z, dsu[r1].l, dsu[r1].r)
                cost[z][dsu[r1].r] += dsu[r1].cost;
        }
    forw(i, 1, m) forw(j, 1, i)
        cost[j][i] += cost[j][i - 1];
    forw(i, 1, m){
        DAC(i, m, i, m, i);
        cout << dp[m][i] << "\n";
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
//    freopen("test.inp","r",stdin);
//    freopen("test.out","w",stdout);
    //time_t TIME_TU=clock();
    int t=1;
//    cin>>t;
    while(t--)
        solve();
    //time_t TIME_TV=clock();
    //cerr<<(db)(TIME_TV-TIME_TU)/CLOCKS_PER_SEC<<endl;
    return 0;
}

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