Submission #855045

#	Time	Username	Problem	Language	Result	Execution time	Memory
855045		12345678	Nafta (COI15_nafta)	C++17	0 / 100	1 ms	4700 KiB

nafta

#include <bits/stdc++.h>

using namespace std;

const int nx=2005;

long long dp[nx][nx], c[nx], mp[nx][nx], n, m, dx[4]={0, 0, 1, -1}, dy[4]={1, -1, 0, 0}, ans[nx], v[nx], sm;
bool vs[nx][nx];
char ch;
vector<bool> t(nx);
queue<int> q;

void dfs(int x, int y, int cr)
{
    vs[x][y]=1;
    if (x<1||x>n||y<1||y>m||mp[x][y]==-1) return;
    if (!t[y]) t[y]=1, q.push(y);
    c[cr]+=mp[x][y];
    sm+=mp[x][y];
    for (int i=0; i<4; i++) if (!vs[x+dx[i]][y+dy[i]]) dfs(x+dx[i], y+dy[i], cr);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) cin>>ch, mp[i][j]=(ch=='.')?-1:ch-'0';
    for (int i=1; i<=m; i++)
    {
        c[i]=c[i-1];
        for (int j=1; j<=n; j++) 
        {
            sm=0;
            if (!vs[j][i]) dfs(j, i, i);
            while (!q.empty()) t[q.front()]=0, v[q.front()]+=sm, q.pop();
        }
    }
    for (int i=1; i<=m; i++)
    {
        for (int j=1; j<=m; j++)
        {
            for (int k=0; k<i; k++)
            {
                dp[i][j]=max(dp[i][j], dp[k][j-1]+min(c[i]-c[k], v[i]));
            }
            ans[j]=max(ans[j], dp[i][j]);
        }
    }
    for (int i=1; i<=m; i++) cout<<ans[i]<<'\n';
}

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