| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 704822 | kelfert | Nafta (COI15_nafta) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <iomanip>
#include <queue>
#include <stack>
#include <random>
#include <chrono>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define pb emplace_back
#define all(x) (x).begin(), (x).end()
typedef long long ll;
const int INF = 2e9;
const int N = 2001;
int cost[N][N], used[N][N], a[N][N], dp[N][N], cnt2[N];
int opt, mid;
void divide(int j, int l, int r, int ql, int qr) {
if (l >= r) return;
mid = (l + r) / 2;
for (int i = ql; i < min(mid, qr); i++) {
if (dp[j][mid] < dp[j - 1][i] + cost[i][mid]) {
dp[j][mid] = dp[j - 1][i] + cost[i][mid];
opt = i;
}
}
divide(j, l, mid, ql, opt + 1);
divide(j, mid + 1, r, opt, qr);
}
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
void dfs(int vx, int vy, int &sum, int &l, int &r) {
used[vx][vy] = 1;
sum += a[vx][vy];
l = min(l, vy);
r = max(r, vy);
for (int k = 0; k < 4; k++) {
int x = vx + dx[k], y = vy + dy[k];
if (!used[x][y] && a[x][y] != -1) {
dfs(x, y, sum, l, r);
}
}
}
const int OPEN = 1;
const int CLOSE = -1;
struct Event {
int x, id, tp, sum;
Event(int x, int id, int tp, int sum) : x(x), id(id), tp(tp), sum(sum) {}
Event() {}
};
bool comp(Event a, Event b) {
return a.x < b.x;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m; cin >> n >> m;
for (int i = 0; i <= n + 1; i++)
for (int j = 0; j <= m + 1; j++)
a[i][j] = -1;
string s;
for (int i = 1; i <= n; i++) {
cin >> s;
for (int j = 0; j < m; j++)
if (s[j] != '.') a[i][j + 1] = (s[j] - '0');
}
vector<Seg> seg;
vector<Event> events;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (!used[i][j] && a[i][j] != -1) {
int sum = 0, l = j, r = j;
dfs(i, j, sum, l, r);
seg.pb(Seg(l, r, sum));
events.pb(Event(l, seg.size() - 1, OPEN, sum));
events.pb(Event(r, seg.size() - 1, CLOSE, sum));
}
}
}
sort(all(events), comp);
for (auto x : events) {
if (x.tp == OPEN) cnt2[x.x] += x.sum;
}
int first = 0;
for (int l = 0; l <= m; l++) {
while (first < events.size() && events[first].x <= l) first++;
int i = first, sum = 0;
for (int r = l; r <= m; r++) {
while (i < events.size() && events[i].x < r) {
if (events[i].tp == OPEN) {
sum += events[i].sum;
} else {
if (seg[events[i].id].l > l) sum -= events[i].sum;
}
i++;
}
cost[l][r] = sum + cnt2[r];
if (l == r) cost[l][r] = 0;
}
}
for (int i = 0; i <= m; i++)
for (int j = 0; j <= m; j++)
dp[i][j] = -INF;
dp[0][0] = 0;
int ans = 0;
for (int j = 1; j <= m; j++) {
divide(j, 0, m + 1, 0, m + 1);
ans = 0;
for (int i = 1; i <= m; i++) ans = max(ans, dp[j][i]);
cout << ans << "\n";
}
return 0;
}