Submission #891806

#TimeUsernameProblemLanguageResultExecution timeMemory
891806chanhchuong123Nafta (COI15_nafta)C++14
100 / 100
293 ms108384 KiB
#include<bits/stdc++.h> using namespace std; #define fi first #define se second #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int Rand(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); } #define ID(x, y) ((x - 1) * nCol + (y - 1)) const int dx[] = {-1, 0, 0, +1}; const int dy[] = {0, -1, +1, 0}; const int INF = 1e9 + 7; const int MAX = 2020; int nRow; int nCol; int f[MAX]; int g[MAX]; char a[MAX][MAX]; int pf[MAX][MAX]; int co[MAX][MAX]; int mn[MAX * MAX]; int mx[MAX * MAX]; int sum[MAX * MAX]; int lab[MAX * MAX]; bool used[MAX * MAX]; int findSet(int v) { return lab[v] < 0 ? v : lab[v] = findSet(lab[v]); } bool unionSet(int u, int v) { u = findSet(u); v = findSet(v); if (u == v) return false; if (lab[u] > lab[v]) swap(u, v); lab[u] += lab[v]; lab[v] = u; mx[u] = max(mx[u], mx[v]); mn[u] = min(mn[u], mn[v]); sum[u] += sum[v]; return true; } void init(void) { cin >> nRow >> nCol; for (int i = 1; i <= nRow; ++i) { for (int j = 1; j <= nCol; ++j) cin >> a[i][j]; } for (int i = 1; i <= nRow; ++i) for (int j = 1; j <= nCol; ++j) if (a[i][j] != '.') { mn[ID(i, j)] = j; mx[ID(i, j)] = j; lab[ID(i, j)] = -1; sum[ID(i, j)] = a[i][j] - '0'; } for (int i = 1; i <= nRow; ++i) for (int j = 1; j <= nCol; ++j) if (a[i][j] != '.') { for (int k = 0; k < 4; ++k) { int x = i + dx[k], y = j + dy[k]; if (x <= 0 || x > nRow) continue; if (y <= 0 || y > nCol) continue; if (a[x][y] != '.') unionSet(ID(i, j), ID(x, y)); } } for (int j = 1; j <= nCol; ++j) { for (int i = 1; i <= nRow; ++i) if (a[i][j] != '.') { int root = findSet(ID(i, j)); if (used[root] == false) { used[root] = true; pf[j][mn[root] + 0] += sum[root]; pf[j][mx[root] + 1] -= sum[root]; } } for (int k = 1; k <= nCol; ++k) { pf[j][k] += pf[j][k - 1]; } for (int i = 1; i <= nRow; ++i) if (a[i][j] != '.') { int root = findSet(ID(i, j)); used[root] = false; } } for (int i = 1; i <= nCol; ++i) { for (int j = i; j <= nCol; ++j) co[i][j] = pf[j][j] - pf[j][i]; } } void calc(int l, int r, int optL, int optR) { if (l > r) return; int mid = l + r >> 1; pair<int, int> best(-INF, -1); for (int k = optL; k <= min(optR, mid - 1); ++k) best = max(best, make_pair(g[k] + co[k][mid], -k)); f[mid] = best.fi; int opt = -best.se; calc(l, mid - 1, optL, opt); calc(mid + 1, r, opt, optR); } void process(void) { for (int i = 1; i <= nCol; ++i) { g[i] = pf[i][i]; f[i] = g[i]; } cout << *max_element(f + 1, f + 1 + nCol) << '\n'; for (int i = 2; i <= nCol; ++i) { calc(1, nCol, 1, nCol); for (int i = 1; i <= nCol; ++i) g[i] = f[i]; cout << *max_element(f + 1, f + 1 + nCol) << '\n'; } } int main(void) { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); init(); process(); return 0; }

Compilation message (stderr)

nafta.cpp: In function 'void calc(int, int, int, int)':
nafta.cpp:92:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |     int mid = l + r >> 1;
      |               ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...