Submission #960573

#	Time	Username	Problem	Language	Result	Execution time	Memory
960573		Niosakaru	Nafta (COI15_nafta)	C++17	100 / 100	871 ms	259104 KiB

nafta

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i,l,r) for (int i = l ; i <= r ; i ++)
#define N 2020

const int mod = 1e9 + 7 , base = 311;

int n , m , s , r , w[N][N] , opt[N][N] , e[N][N] , a[N][N] , vs[N][N] , rs[N] , dp[N][N] , dx[] = {0,0,-1,1} , dy[] = {1,-1,0,0};

int bfs(int u,int v){
    r = max(r,v); vs[u][v] = 1;
    int sum = a[u][v];
    rep(i,0,3){
        int x = u + dx[i] , y = v + dy[i];
        if (1 > x || 1 > y || n < x || m < y || vs[x][y] || a[x][y] == -1) continue;
        sum += bfs(x,y);
    }
    return sum;
}

signed main(){
    cin.tie(NULL)->sync_with_stdio(NULL);

    cin >> n >> m;
    memset(a , -1 , sizeof a);
    rep(i,1,n) rep(j,1,m)
    {
        char c; cin >> c;
        if (c == '.') continue;
        a[i][j] = c - '0';
    }

    rep(j,1,m) rep(i,1,n)
    {
        if (vs[i][j] || a[i][j] == -1) continue;
        r = j , s = bfs(i,j);
        w[j][r] += s;
    }

    for (int i = m ; i ; i --){
        s = 0;
        for (int j = m ; j >= i ; j --){
            s += w[i][j];
            e[i][j] = e[i + 1][j] + s;
        }
    }

    rep(k,1,m){
        rep(i,1,m){
            int Le = max(opt[i][k-1],opt[i-1][k]) , Ri = i;
            if (k == 1) Le = Ri = 1;
            rep(j,Le,Ri){
                s = dp[j - 1][k - 1] + e[j][i];
                if (s > dp[i][k]){
                    dp[i][k] = s;
                    opt[i][k] = j;
                }
            }
            rs[k] = max(rs[k] , dp[i][k]);
        }
    }

    rep(i,1,m)
        cout << rs[i] << '\n';
}

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