Submission #992534

#	Time	Username	Problem	Language	Result	Execution time	Memory
992534		Khanhcsp2	Nafta (COI15_nafta)	C++14	100 / 100	243 ms	163664 KiB

nafta

#include<bits/stdc++.h>
#define el '\n'
#define fi first
#define sc second
#define int ll
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
const int mod=1e9+7;
const int N=2e3+11;
int hx[]={0, 0, -1, 1};
int hy[]={-1, 1, 0, 0};
int m, n;
char a[N][N];
int v[N][N], vit[N][N], l[N], r[N], val[N], mi=N, sum, ma, s[N][N];
vector<int> dp1, dp2;
bool valid(int x, int y)
{
    if(x<1 || x>m || y<1 || y>n || vit[x][y]) return 0;
    return 1;
}
void dfs(int i, int j)
{
    if(vit[i][j]) return;
    vit[i][j]=1;
    sum+=v[i][j];
    mi=min(mi, j);
    ma=max(ma, j);
    for(int q=0;q<=3;q++)
    {
        int x=i+hx[q], y=j+hy[q];
        if(valid(x, y))
        {
             dfs(x, y);
        }
    }
}
int calc(int l, int r)
{
    return s[l][r];
}
void dnc(int l, int r, int lll, int rrr)
{
    if(l>r) return;
    int mid=(l+r)/2;
    pii s= {0, -1};
    for(int i=lll; i<=min(mid, rrr); i++) s = max(s, {dp1[i]+calc(i+1, mid),i});
    dp2[mid]=s.fi;
    int opt=s.sc;
    dnc(l, mid-1, lll, opt);
    dnc(mid+1, r, opt, rrr);
}
void sol()
{
    cin >> m >> n;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin >> a[i][j];
            if(a[i][j]=='.') vit[i][j]=1;
            else v[i][j]=a[i][j]-'0';
        }
    }
    dp1.resize(n+11, 0);
    dp2.resize(n+11, 0);
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(vit[i][j]) continue;
            ma=0, mi=N, sum=0;
            dfs(i, j);
            for(int _=mi;_<=ma;_++)
            {
                dp1[_]+=sum;
                s[1][_]+=sum;
                s[mi+1][_]-=sum;
            }
        }
    }
    for(int i=0;i<=n;i++) for(int j=1;j<=n;j++) s[j][i]+=s[j-1][i];
    int ans=0;
    for(int i=1;i<=n;i++) ans=max(ans, dp1[i]);
    cout << ans << el;
    for(int i=2; i<=n; i++)
    {
        dnc(i, n, i-1, n-1);
        int ans=0;
        for(int j=1; j<=n; j++) dp1[j]=dp2[j], dp2[j]=0, ans=max(ans, dp1[j]);
        cout << ans << el;
    }
}
signed main()
{
//    freopen("divisor.INP", "r", stdin);
//    freopen("divisor.OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin >> t;
    while(t--)
    {
        sol();
    }
}

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