제출 #780921

#제출 시각아이디문제언어결과실행 시간메모리
780921IvkosqnNafta (COI15_nafta)C++14
11 / 100
1065 ms2388 KiB
#include <bits/stdc++.h> #define endl '\n' using namespace std; const int maxn = 2010; int n, m, used[maxn][maxn]; char c[maxn][maxn]; vector<long long> dp_bef(maxn), dp_aft(maxn); struct cell{ int x, y; cell operator+(cell c){ return {x + c.x, y + c.y}; } bool inRange(){ return x >= 1 && x <= n && y >= 1 && y <= m; } }; cell dir[4] = { {0, -1}, {0, 1}, {-1, 0}, {1, 0} }; void read(){ cin >> n >> m; for(int i = 1;i <= n;i++){ for(int j = 1;j <= m;j++){ cin >> c[i][j]; } } } void bfs(cell beg, int col){ queue<cell> q; q.push(beg); used[beg.x][beg.y] = col; while(!q.empty()){ cell e = q.front(); q.pop(); for(int i = 0;i < 4;i++){ cell curr = e + dir[i]; if(!curr.inRange() || used[curr.x][curr.y]) continue; if(c[curr.x][curr.y] == '.') continue; used[curr.x][curr.y] = col; q.push(curr); } } } void preCompute(){ int cnt = 1; for(int i = 1;i <= n;i++){ for(int j = 1;j <= m;j++){ if(c[i][j] != '.' && !used[i][j]){ bfs({i, j}, cnt); cnt++; } } } assert(cnt <= 2000); memset(used, 0, sizeof(used)); } int cycle = 1, s; long long calc(int i, int mid){ long long sum = 0; queue<cell> q; cycle++; for(int j = 1;j <= n;j++){ if(mid <= m && c[j][mid] != '.'){ q.push({j, mid}); used[j][mid] = cycle; sum += c[j][mid] - '0'; } } s = sum; while(!q.empty()){ cell t = q.front(); q.pop(); for(int j = 0;j < 4;j++){ cell curr = dir[j] + t; if(!curr.inRange() || used[curr.x][curr.y] == cycle) continue; if(c[curr.x][curr.y] == '.' || curr.y > mid || curr.y <= i) continue; sum += c[curr.x][curr.y] - '0'; q.push(curr); used[curr.x][curr.y] = cycle; } } if(i == 0) return sum; q = queue<cell>(); for(int j = 1;j <= n;j++){ if(c[j][i] != '.' && used[j][i] != cycle){ q.push({j, i}); used[j][i] = cycle; } } while(!q.empty()){ cell t = q.front(); q.pop(); for(int j = 0;j < 4;j++){ cell curr = dir[j] + t; if(!curr.inRange() || used[curr.x][curr.y] == cycle) continue; if(c[curr.x][curr.y] == '.' || curr.y > mid || curr.y <= i) continue; sum += c[curr.x][curr.y] - '0'; q.push(curr); used[curr.x][curr.y] = cycle; } } return sum; } void divide(int l, int r, int optl, int optr){ if(l > r) return; int mid = (l + r) / 2; long long best = LLONG_MIN, k; for(int i = optl;i <= min(mid, optr);i++){ long long curr = dp_bef[i - 1] + calc(i - 1, mid); if(curr > best){ best = curr; k = i; } } dp_aft[mid] = best; divide(l, mid - 1, optl, k); divide(mid + 1, r, k, optr); } void solve(){ long long ans = 0; for(int i = 1;i <= m;i++){ dp_bef[i] = calc(0, i); ans = max(ans, dp_bef[i] + calc(i, m + 1) - s); } cout << ans << endl; for(int i = 2;i <= m;i++){ divide(1, m, 1, m); dp_bef = dp_aft; long long ans = 0; for(int i = 1;i <= m;i++){ ans = max(ans, dp_aft[i] + calc(i, m + 1) - s); } cout << ans << endl; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); read(); solve(); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

nafta.cpp: In function 'void divide(int, int, int, int)':
nafta.cpp:134:11: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
  134 |     divide(l, mid - 1, optl, k);
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...