Submission #351585

#	Time	Username	Problem	Language	Result	Execution time	Memory
351585		gmyu	Nafta (COI15_nafta)	C++14	0 / 100	20 ms	32620 KiB

nafta

/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/COI15_nafta
*/
#include <iostream>  //cin , cout
#include <fstream>   //fin, fout
#include <stdio.h>   // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack>     // stacks
#include <queue>     // queues
#include <map>
#include <string>
#include <set>
#include <string.h>


using namespace std;

typedef pair<int, int>          pii;
typedef vector<int>             vi;     /// adjlist without weight
typedef vector<pii>             vii;    /// adjlist with weight
typedef vector<pair<int,pii>>   vpip;   /// edge with weight
typedef long long               ll;

#define mp  make_pair
#define fst first
#define snd second
#define pb  push_back
#define sz(x) (int)(x).size()
#define trav(u, adj_v) for (auto& u: adj_v)

const int MOD = 1e9+7;  // 998244353;
const int MX  = 2e5+5;   //
const ll  INF = 1e18;    //

#define MAXV 2007
#define MAXE 100007

const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions

bool debug;

int N;
int numRow, numCol;
int a[MAXV][MAXV], visited[MAXV][MAXV];
int cost[MAXV][MAXV];
int val, mxc;
ll dp[MAXV][MAXV];
ll mxdp;

bool oob(int r, int c) {
    if (1<=r && r<=numRow && 1<=c && c<=numCol) return false;
    return true;
}
void dfs(int r, int c) {
    if(visited[r][c] || a[r][c]==-1) return;
    visited[r][c] = 1;
    val += a[r][c]; mxc = max(mxc, c);
    for(int i=0; i<4; i++) {
        int nr = r + xdir[i], nc = c + ydir[i];
        if(!oob(nr, nc) && !visited[nr][nc] && a[nr][nc]!=-1) dfs(nr, nc);
    }
}

void cal2DPreSum(){
    /// dfs to find the point value
    for(int i=1;i<=numRow;i++) {
        for(int j=1; j<=numCol; j++) {
            if(visited[i][j]) continue;
            val=0; mxc = 0;
            dfs(i, j);
            cost[j][mxc] += val;
        }
    }
    /// do pre-sum
    for(int i=1;i<=numCol;i++) {
        for(int j=1; j<=numCol; j++) {
            cost[i][j] = cost[i][j] + cost[i-1][j] + cost[i][j-1] - cost[i-1][j-1];
        }
    }

}


void solve(int k, int l, int r, int optl, int optr) {
    if(l>r) return;

    int mid = (l+r)/2;
    int nopt = mid;
    dp[k][mid] = dp[k-1][mid];
    for(int j= optl; j+1<=mid && j<=optr; j++) {
        ll cost1 = cost[mid][numCol] - cost[j][numCol] - cost[mid][mid-1] + cost[j][mid-1];
        if(dp[k-1][j] + cost1 > dp[k][mid]) {
            dp[k][mid] = dp[k-1][j] + cost1;
            nopt = j;
        }
    }
    mxdp = max(mxdp, dp[k][mid]);

    if(l==r) return;
    solve(k, l, mid-1, optl, nopt);
    solve(k, mid+1, r, nopt, optr);
}

int main() {
    debug = true;
    ios_base::sync_with_stdio(false); cin.tie(0);

    int i, j, k;

    cin >> numRow >> numCol ;
    for(i = 1; i<=numRow; i++) {
        string c; cin >> c;
        for(j=0;j<numCol; j++)
            a[i][j+1] = (c[j]=='.') ? (-1) : (c[j]-'0');
    }
    cal2DPreSum();

    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0LL;
    for(k = 1; k<=numCol; k++) {
        mxdp = 0LL;
        solve(k, 1, numCol, 0, numCol);
        cout << mxdp << endl;
    }

}

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