제출 #416756

#제출 시각아이디문제언어결과실행 시간메모리
416756JerryLiu06Nafta (COI15_nafta)C++17
100 / 100
416 ms84288 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using db = long double; using str = string; using pi = pair<int, int>; using pl = pair<ll, ll>; using pd = pair<db, db>; using vi = vector<int>; using vb = vector<bool>; using vl = vector<ll>; using vd = vector<db>; using vs = vector<str>; using vpi = vector<pi>; using vpl = vector<pl>; using vpd = vector<pd>; #define mp make_pair #define f first #define s second #define sz(x) (int)(x).size() #define bg(x) begin(x) #define all(x) bg(x), end(x) #define sor(x) sort(all(x)) #define ft front() #define bk back() #define pb push_back #define pf push_front #define lb lower_bound #define ub upper_bound #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define F0R(i, a) FOR(i, 0, a) #define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--) #define R0F(i, a) ROF(i, 0, a) #define EACH(a, x) for (auto& a : x) const int MOD = 1e9 + 7; const int MX = 2e3 + 10; const ll INF = 1e18; int R, S; string grid[MX]; int pref[MX][MX]; pi bound; int sum, tot; bool vis[MX][MX]; int DP[MX][MX]; void DFS(int x, int y) { if (x < 0 || x >= R || y < 0 || y >= S || vis[x][y] || grid[x][y] == '.') return ; bound.f = min(bound.f, y); bound.s = max(bound.s, y); vis[x][y] = true; sum += grid[x][y] - '0'; DFS(x + 1, y); DFS(x, y + 1); DFS(x - 1, y); DFS(x, y - 1); } void solve(int k, int l, int r, int optl, int optr) { if (l > r) return ; int mid = (l + r) / 2; pi BEST = {MOD, -1}; FOR(i, optl, min(mid, optr) + 1) { BEST = min(BEST, {DP[i][k - 1] + pref[i + 1][mid - 1], i}); } DP[mid][k] = BEST.f; int opt = BEST.s; solve(k, l, mid - 1, optl, opt); solve(k, mid + 1, r, opt, optr); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> R >> S; F0R(i, R) cin >> grid[i]; F0R(i, R) F0R(j, S) if (grid[i][j] != '.' && !vis[i][j]) { bound = {MOD, -MOD}; sum = 0; DFS(i, j); pref[bound.f + 1][bound.s + 1] += sum; tot += sum; } ROF(i, 1, S + 1) FOR(j, 1, S + 1) { pref[i][j] += pref[i + 1][j]; pref[i][j] += pref[i][j - 1]; pref[i][j] -= pref[i + 1][j - 1]; // Overcount by PIE } FOR(i, 1, S + 2) DP[i][0] = MOD; FOR(k, 1, S + 2) { solve(k, 0, S + 1, 0, S); int ans = 0; if (k > 1) cout << tot - DP[S + 1][k] << "\n"; } }

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

nafta.cpp: In function 'void solve(int, int, int, int, int)':
nafta.cpp:61:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   61 |     if (l > r) return ; int mid = (l + r) / 2; pi BEST = {MOD, -1};
      |     ^~
nafta.cpp:61:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   61 |     if (l > r) return ; int mid = (l + r) / 2; pi BEST = {MOD, -1};
      |                         ^~~
nafta.cpp: In function 'int main()':
nafta.cpp:87:39: warning: unused variable 'ans' [-Wunused-variable]
   87 |         solve(k, 0, S + 1, 0, S); int ans = 0;
      |                                       ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...