| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1278108 | g4yuhg | Nafta (COI15_nafta) | C++20 | 0 ms | 0 KiB |
//Huyduocdithitp
#include<bits/stdc++.h>
typedef int ll;
#define endl '\n'
#define fi first
#define se second
#define pii pair<ll,ll>
#define N 2005
#define LOG 18
using namespace std;
const ll inf = 1e9;
bool ghuy4g;
const ll hx[] = {1, -1, 0, 0};
const ll hy[] = {0, 0, 1, -1};
ll n, m;
ll b[N * N], par[N * N], cur, cur2, ax[N][N], L[N * N], R[N * N], sum[N * N];
ll cost[N][N];
pii p[N * N];
ll find(ll u) {
if (par[u] < 0) return u;
return par[u] = find(par[u]);
}
void join(ll u, ll v) {
u = find(u);
v = find(v);
if (u == v) return;
if (par[u] <= par[v]) {
par[u] += par[v];
par[v] = u;
}
else {
par[v] += par[u];
par[u] = v;
}
}
char a[N][N];
struct piii {
ll l, r, val;
};
bool cmp (piii a, piii b) {
return a.l < b.l;
}
ll st[4 * N];
void update(ll id, ll l, ll r, ll i, ll v) {
if (i > r || i < l) return;
if (l == r) {
st[id] += v;
return;
}
ll mid = (l + r) / 2;
update(id * 2, l, mid, i, v);
update(id * 2 + 1, mid + 1, r, i, v);
st[id] = st[id * 2] + st[id * 2 + 1];
}
ll get(ll id, ll l, ll r, ll L, ll R) {
if (l > R || r < L) return 0;
if (L <= l && r <= R) return st[id];
ll mid = (l + r) / 2;
return get(id * 2, l, mid, L, R) + get(id * 2 + 1, mid + 1, r, L, R);
}
ll dp[2005][2005];
void sub1() {
ll ans = 0;
for (int id = 1; id <= m; id ++) {
for (int i = 1; i <= m; i ++) {
ll jtoi = 0;
for (int j = 0; j < i; j ++) {
dp[id][i] = max(dp[id][i], dp[id - 1][j] + cost[j][i]);
ans = max(ans, dp[id][i]);
if (dp[id][i] == dp[id - 1][j] + cost[j][i]) {
jtoi = j;
}
}
//cout << i << " jtoi " << jtoi << endl;
}
cout << ans << endl;
}
}
ll res = 0;
void dnc(ll id, ll l, ll r, ll L, ll R) {
if (l > r) return;
if (L > R) return;
ll mid = (l + r) / 2;
ll bd = max(0LL, L);
ll en = min(R, mid - 1);
ll i = mid, jtoi = 0;;
for (int j = bd; j <= en; j ++) {
dp[id][i] = max(dp[id][i], dp[id - 1][j] + cost[j][i]);
//cout << dp[id - 1][j] + cost[j][i] << " j " << j << endl;
if (dp[id][i] == dp[id - 1][j] + cost[j][i]) {
jtoi = j;
}
res = max(res, dp[id][i]);
}
//cout << "id " << i << " " << jtoi << " " << dp[id][mid] << " " << cost[0][mid] << endl;
dnc(id, l, mid - 1, L, jtoi);
dnc(id, mid + 1, r, jtoi, R);
}
void sub2() {
for (int id = 1; id <= m; id ++) {
dnc(id, 1, m, 0, m - 1);
cout << res << endl;
}
}
void pre() {
map<ll, ll> mp;
for (int i = 1; i <= cur; i ++) {
ll r = find(i);
if (mp[r] == 0) {
mp[r] = ++ cur2;
sum[mp[r]] = 0;
L[mp[r]] = inf;
R[mp[r]] = -inf;
}
sum[mp[r]] += b[i];
L[mp[r]] = min(L[mp[r]], p[i].se);
R[mp[r]] = max(R[mp[r]], p[i].se);
}
vector<piii> vt;
for (int i = 1; i <= cur2; i ++) {
vt.push_back({L[i], R[i], sum[i]});
}
sort(vt.begin(), vt.end(), cmp);
/*for (auto it : vt) {
cout << it.l << " " << it.r << " " << it.val << endl;
}*/
ll pt = 0;
priority_queue<pii, vector<pii>, greater<pii>> pq;
for (int i = 1; i <= m; i ++) {
//cout << "den " << i << endl;
while (pt < vt.size() && vt[pt].l <= i) {
update(1, 1, m, vt[pt].l, vt[pt].val);
//cout << "add " << vt[pt].l << " " << vt[pt].r << " " << vt[pt].val << endl;
pq.push({vt[pt].r, pt});
pt ++ ;
}
while (pq.size() && pq.top().fi < i) {
ll id = pq.top().se;
update(1, 1, m, vt[id].l, -vt[id].val);
pq.pop();
}
for (int j = i - 1; j >= 0; j --) {
cost[j][i] = get(1, 1, m, j + 1, i);
//cout << j << " " << i << " " << cost[j][i] << endl;
}
}
}
bool klinh;
signed main() {
//freopen("test.inp", "r", stdin);
//freopen("test.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
memset(par, -1, sizeof(par));
cin >> n >> m;
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
cin >> a[i][j];
if ('0' <= a[i][j] && a[i][j] <= '9') {
b[++ cur] = a[i][j] - '0';
p[cur] = {i, j};
ax[i][j] = cur;
}
}
}
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
if ('0' <= a[i][j] && a[i][j] <= '9') {
for (int z = 0; z < 4; z ++) {
ll dx = i + hx[z];
ll dy = j + hy[z];
if (dx < 1 || dy < 1 || dx > n || dy > m || !('0' <= a[dx][dy] && a[dx][dy] <= '9')) {
continue;
}
join(ax[i][j], ax[dx][dy]);
}
}
}
}
pre();
sub2();
cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
return 0;
}