Submission #1291479

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291479		DangKhoizzzz	Nafta (COI15_nafta)	C++20	0 / 100	1 ms	1080 KiB

nafta

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>

using namespace std;

const int INF = 1e18;
const int maxn = 2e3 + 7;


int dx[4] = {1 , -1 , 0 , 0};
int dy[4] = {0 , 0 , -1 , 1};

int n , m , a[2002][2002] , mnl[2002][2002] , mxr[2002][2002], cnt[2002][2002];

void dfs1(int i , int j , int c)
{
    mnl[i][j] = c;
    for(int k = 0; k < 4; k++)
    {
        int x = i + dx[k];
        int y = j + dy[k];
        if(x <= 0 || x > n || y <= 0 || y > m || a[x][y] == -1 || mnl[x][y] == c) continue;
        dfs1(x , y , c);
    }
}

void dfs2(int i , int j , int c)
{
    mxr[i][j] = c;
    for(int k = 0; k < 4; k++)
    {
        int x = i + dx[k];
        int y = j + dy[k];
        if(x <= 0 || x > n || y <= 0 || y > m || a[x][y] == -1 || mxr[x][y] == c) continue;
        dfs2(x , y , c);
    }
}

int cost(int l , int r)
{
    if(l > r) return 0;
    return cnt[r][r] + cnt[l-1][l-1] - cnt[l-1][r] - cnt[r][l-1];
}

int dp[2][maxn];

void compute(int t , int l , int r , int optl , int optr)
{
    if(r > l) return;
    int mid = (l+r) >> 1;
    pii best = {INF , INF};
    for(int i = optl; i <= min(mid-1 , optr); i++)
    {
        best = min(best , {dp[t^1][i] + cost(i+1 , mid-1) , i});
    }
    dp[t][mid] = best.fi;
    compute(t , l , mid-1 , optl , best.se);
    compute(t , mid+1 , r , best.se , optr);
}

void solve()
{
    cin >> n >> m;
    int sum = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++) 
        {
            char c; cin >> c;
            if(c == '.') a[i][j] = -1;
            else a[i][j] = c - '0';
            sum += max(0ll , a[i][j]);
        }
    }
    for(int j = 1; j <= m; j++)
    {
        for(int i = 1; i <= n; i++)
        {
            if(a[i][j] != -1)
            {
                if(mnl[i][j] == 0) dfs1(i , j , j);
            }
        }
    }
    for(int j = m; j >= 1; j--)
    {
        for(int i = 1; i <= n; i++)
        {
            if(a[i][j] != -1)
            {
                if(mxr[i][j] == 0) dfs2(i , j , j);
            }
        }
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(a[i][j] != -1) cnt[mnl[i][j]][mxr[i][j]] += a[i][j];
        }
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cnt[i][j] += cnt[i-1][j] + cnt[i][j-1] - cnt[i-1][j-1]; 
        }
    }
    for(int i = 1; i <= m+1; i++) dp[0][i] = dp[1][i] = INF;
    int preans = INF;
    for(int i = 1; i <= m; i++) 
    {
        compute(i&1 , 1 , m+1 , 0 , m);
        int ans = max(preans , sum - dp[i&1][m+1]);
        cout << ans << '\n';
        preans = ans;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    //freopen("inp.txt", "r" , stdin);
    //freopen("out.txt", "w" , stdout);
    solve();
    return 0;
}

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