제출 #971733

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
971733		dwuy	Nafta (COI15_nafta)	C++14	34 / 100	6 ms	12120 KiB

nafta

/**   - dwuy -

　　　　　 ／＞　   フ
　　　　　 | 　_　 _|
　 　　　 ／`ミ _x ノ
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ

**/
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t((s).size())
#define MASK(k)(1LL<<(k))
#define TASK "test"
#define int long long

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 1005;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

int n, m;
int val[MX][MX];
int cost[MX][MX];
int f[MX][MX];
string a[MX];

void nhap(){
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        a[i] = ' ' + a[i];
    }
}

void dfs(int x, int y, int &L, int &R, int &sum){
    sum += a[x][y] - '0';
    L = min(L, y);
    R = max(R, y);
    a[x][y] = '.';
    for(int i=0; i<4; i++){
        int u = x + dx[i];
        int v = y + dy[i];
        if(u<1 || u>n || v<1 || v>m || a[u][v] == '.') continue;
        dfs(u, v, L, R, sum);
    }
}

void dwuy(int id, int l, int r, int fx, int fy){
    if(l > r) return;
    int mid = (l + r)>>1;
    pii best = {-1, 0};
    for(int i=fx; i<=min(mid, fy); i++){
        best = max(best, {f[id-1][i] + cost[i+1][mid], i});
    }
    f[id][mid] = best.fi;
    dwuy(id, l, mid-1, fx, best.se);
    dwuy(id, mid+1, r, best.se, fy);
}

void solve(){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(a[i][j] == '.') continue;
            int L = j, R = j, sum = 0;
            dfs(i, j, L, R, sum);
            val[L][R] += sum;
        }
    }
    for(int i=1; i<=m; i++){
        for(int j=m; j>=i; j--){
            val[i][j] += val[i][j+1];
        }
    }
    for(int i=1; i<=m; i++){
        for(int j=i; j>=1; j--){
            cost[j][i] = cost[j+1][i] + val[j][i];
        }
    }
    
    for(int i=1; i<=m; i++) f[1][i] = cost[1][i];
    for(int i=2; i<=m; i++){
        dwuy(i, i, m, i-1, m);
    }
    for(int i=1; i<=m; i++){
        int ans = 0;
        for(int j=1; j<=m; j++) ans = max(ans, f[i][j]);
        cout << ans << '\n';
    }
}

int32_t main(){
    fastIO;
    //file(TASK);

    nhap();
    solve();

    return 0;
}

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