Submission #351591

#TimeUsernameProblemLanguageResultExecution timeMemory
351591gmyuNafta (COI15_nafta)C++14
0 / 100
10 ms16768 KiB
/* 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; int dp[MAXV][MAXV]; int 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++) { int 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] = 0; for(k = 1; k<=numCol; k++) { mxdp = 0; solve(k, 1, numCol, 0, numCol); cout << mxdp << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...