| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 704818 | 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("Ofast")
#pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native" )
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
#pragma GCC optimize("vpt")
#pragma GCC optimize("rename-registers")
#pragma GCC optimize("move-loop-invariants")
#pragma GCC optimize("unswitch-loops")
#pragma GCC optimize("function-sections")
#pragma GCC optimize("branch-target-load-optimize")
#pragma GCC optimize("branch-target-load-optimize2")
#pragma GCC optimize("btr-bb-exclusive")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#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 F first
#define S second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
typedef long long ll;
const ll MOD = 1e9 + 7;
const int INF = 2e9;
const int N = 2010;
int cost[N][N], used[N][N], a[N][N], dp[N][N], cnt2[N];
void divide(int j, int l, int r, int ql, int qr) {
if (l >= r) return;
int m = (l + r) / 2;
int opt;
for (int i = ql; i < min(m, qr); i++) {
if (dp[j][m] < dp[j - 1][i] + cost[i][m]) {
dp[j][m] = dp[j - 1][i] + cost[i][m];
opt = i;
}
}
divide(j, l, m, ql, opt + 1);
divide(j, m + 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 Seg {
int l, r, sum;
Seg(int l, int r, int sum) : l(l), r(r), sum(sum) {}
Seg() {}
};
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;
}