Submission #777648

#	Time	Username	Problem	Language	Result	Execution time	Memory
777648		serkanrashid	Nafta (COI15_nafta)	C++14	34 / 100	1067 ms	71592 KiB

nafta

#include <bits/stdc++.h>
#define endl "\n"

using namespace std;

struct Point
{
    int x,y;
    Point(){};
    Point(int xi, int yi)
    {
        x = xi;
        y = yi;
    }
    Point operator+(Point ed)
    {
        Point res;
        res.x = x + ed.x;
        res.y = y + ed.y;
        return res;
    }
};

const int maxn = 2005;

int n,m;
int a[maxn][maxn],used[maxn][maxn];
bool vis[maxn*maxn];
long long mat[maxn][maxn],sum[maxn*maxn];
Point dir[4] = {{1,0},{-1,0},{0,1},{0,-1}};
vector<long long>dp_bef,dp_cur;
long long ans;
int idx;

void read()
{
    memset(mat,-1,sizeof(mat));
    cin >> n >> m;
    char z;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin >> z;
            if(z=='.') used[i][j] = -1;
            else a[i][j] = z-'0';
        }
    }
    for(int i=0;i<=n+1;i++) used[i][0] = used[i][m+1] = -1;
    for(int j=0;j<=m+1;j++) used[0][j] = used[n+1][j] = -1;
}

void dfs(Point beg)
{
    used[beg.x][beg.y] = idx;
    sum[idx] += a[beg.x][beg.y];
    Point nb;
    for(int i=0;i<4;i++)
    {
        nb = beg + dir[i];
        if(!used[nb.x][nb.y]) dfs(nb);
    }
}

void pre()
{
    for(int j=1;j<=m;j++)
    {
        for(int i=1;i<=n;i++)
        {
            if(!used[i][j])
            {
                idx++;
                dfs({i,j});
            }
        }
    }
    dp_bef.clear();
    dp_cur.clear();
    dp_bef.resize(m+1);
    dp_cur.resize(m+1);
}

long long cost(int l, int r)
{
    if(mat[l][r]!=-1) return mat[l][r];
    long long oil = 0;
    for(int i=1;i<=n;i++)
    {
        if(used[i][l]==-1) continue;
        vis[used[i][l]] = 1;
    }
    for(int i=1;i<=n;i++)
    {
        if(used[i][r]==-1) continue;
        if(!vis[used[i][r]]) oil += sum[used[i][r]];
        vis[used[i][r]] = 1;
    }
    for(int i=1;i<=n;i++)
    {
        if(used[i][l]!=-1) vis[used[i][l]] = 0;
        if(used[i][r]!=-1) vis[used[i][r]] = 0;
    }
    mat[l][r] = oil;
    return oil;
}

void divide(int l, int r, int optl, int optr)
{
    if(l>r) return;
    int mid = (l+r)/2;
    pair<long long, int> best = {0,-1};
    for(int i=optl;i<=min(mid,optr);i++)
    {
        long long pom = dp_bef[i] + cost(i,mid);
        if(pom>best.first) best = {pom,i};
    }
    dp_cur[mid] = best.first;
    ans = max(ans,dp_cur[mid]);
    int opt = best.second;
    divide(l,mid-1,optl,opt);
    divide(mid+1,r,opt,optr);
}

void solve()
{
    pre();
    for(int i=1;i<=m;i++)
    {
        dp_bef[i] = cost(0,i);
        ans = max(ans,dp_bef[i]);
    }
    cout << ans << endl;
    for(int j=2;j<=m;j++)
    {
        divide(1,m,1,m);
        dp_bef = dp_cur;
        cout << ans << endl;
    }
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	read();
	solve();
return 0;
}

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