Submission #1200220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200220		Muhammad_Aneeq	Nafta (COI15_nafta)	C++20	100 / 100	365 ms	96968 KiB

nafta

#include <iostream>
#include <vector>
#include <set>
using namespace std;
int const N=2e3+10;
char a[N][N]={};
bool vis[N][N]={};
set<int>cur;
int x[4]={1,-1,0,0},y[4]={0,0,1,-1};
int n,m;
int ov[N][N]={};
int dp[N][N]={};
bool check(int i,int j)
{
    if (min(i,j)<0||i>=n||j>=m||a[i][j]=='.'||vis[i][j])
        return 0;
    return 1;
}
int sm=0;
void dfs(int i,int j)
{   
    cur.insert(j+1); 
    vis[i][j]=1;
    sm+=(a[i][j]-'0');
    for (int k=0;k<4;k++)
    {
        if (check(i+x[k],j+y[k]))
            dfs(i+x[k],j+y[k]);
    }
}
void comp(vector<int>z)
{
    int x=z.size();
    for (auto i:z)
        ov[i][z[0]]+=sm;
}
int cost(int l,int r)
{
    return ov[r][l+1];
}
void divi(int st,int en,int k,int l,int r)
{
    if (st>en)
        return;
    int opt=l;
    int mid=(st+en)/2;
    for (int j=l;j<=r && j<mid;j++)
    {
        if (dp[j][k-1]+cost(j,mid)>dp[opt][k-1]+cost(opt,mid))
            opt=j;
    }
    dp[mid][k]=dp[opt][k-1]+cost(opt,mid);
    divi(st,mid-1,k,l,opt);
    divi(mid+1,en,k,opt,r);
}
inline void solve()
{
    cin>>n>>m;
    for (int i=0;i<n;i++)
        for (int j=0;j<m;j++)
            cin>>a[i][j];
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<m;j++)
        {
            if (!vis[i][j]&&a[i][j]!='.')
            {
                sm=0;
                cur={};
                dfs(i,j);
                vector<int>z={begin(cur),end(cur)};
                comp(z);
            }
        }
    }
    for (int i=1;i<=m;i++)
        for (int j=i;j>0;j--)
            ov[i][j-1]+=ov[i][j];
    for (int i=1;i<=m;i++)
    {
        divi(1,m,i,0,m);
        int ans=0;
        for (int j=1;j<=m;j++)
            ans=max(ans,dp[j][i]);
        cout<<ans<<endl;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    for (int i=1;i<=t;i++)
    {
        solve();
    }
}

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