#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native" )
#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 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;
}
Compilation message
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/gthr.h:148,
from /usr/include/c++/10/ext/atomicity.h:35,
from /usr/include/c++/10/bits/ios_base.h:39,
from /usr/include/c++/10/ios:42,
from /usr/include/c++/10/ostream:38,
from /usr/include/c++/10/iostream:39,
from nafta.cpp:6:
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:102:1: error: attribute value 'tune=native' was already specified in 'target' attribute
102 | __gthrw(pthread_once)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:102:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:103:1: error: attribute value 'tune=native' was already specified in 'target' attribute
103 | __gthrw(pthread_getspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:103:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:104:1: error: attribute value 'tune=native' was already specified in 'target' attribute
104 | __gthrw(pthread_setspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:104:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:106:1: error: attribute value 'tune=native' was already specified in 'target' attribute
106 | __gthrw(pthread_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:106:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:107:1: error: attribute value 'tune=native' was already specified in 'target' attribute
107 | __gthrw(pthread_join)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:107:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:108:1: error: attribute value 'tune=native' was already specified in 'target' attribute
108 | __gthrw(pthread_equal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:108:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:109:1: error: attribute value 'tune=native' was already specified in 'target' attribute
109 | __gthrw(pthread_self)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:109:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:110:1: error: attribute value 'tune=native' was already specified in 'target' attribute
110 | __gthrw(pthread_detach)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:110:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:112:1: error: attribute value 'tune=native' was already specified in 'target' attribute
112 | __gthrw(pthread_cancel)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:112:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:114:1: error: attribute value 'tune=native' was already specified in 'target' attribute
114 | __gthrw(sched_yield)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:114:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:116:1: error: attribute value 'tune=native' was already specified in 'target' attribute
116 | __gthrw(pthread_mutex_lock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:116:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:117:1: error: attribute value 'tune=native' was already specified in 'target' attribute
117 | __gthrw(pthread_mutex_trylock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:117:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:119:1: error: attribute value 'tune=native' was already specified in 'target' attribute
119 | __gthrw(pthread_mutex_timedlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:119:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:121:1: error: attribute value 'tune=native' was already specified in 'target' attribute
121 | __gthrw(pthread_mutex_unlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:121:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:122:1: error: attribute value 'tune=native' was already specified in 'target' attribute
122 | __gthrw(pthread_mutex_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:122:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:123:1: error: attribute value 'tune=native' was already specified in 'target' attribute
123 | __gthrw(pthread_mutex_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:123:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:125:1: error: attribute value 'tune=native' was already specified in 'target' attribute
125 | __gthrw(pthread_cond_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:125:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:126:1: error: attribute value 'tune=native' was already specified in 'target' attribute
126 | __gthrw(pthread_cond_broadcast)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:126:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:127:1: error: attribute value 'tune=native' was already specified in 'target' attribute
127 | __gthrw(pthread_cond_signal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:127:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:128:1: error: attribute value 'tune=native' was already specified in 'target' attribute
128 | __gthrw(pthread_cond_wait)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:128:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:129:1: error: attribute value 'tune=native' was already specified in 'target' attribute
129 | __gthrw(pthread_cond_timedwait)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:129:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:130:1: error: attribute value 'tune=native' was already specified in 'target' attribute
130 | __gthrw(pthread_cond_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:130:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:132:1: error: attribute value 'tune=native' was already specified in 'target' attribute
132 | __gthrw(pthread_key_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:132:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:133:1: error: attribute value 'tune=native' was already specified in 'target' attribute
133 | __gthrw(pthread_key_delete)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:133:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:134:1: error: attribute value 'tune=native' was already specified in 'target' attribute
134 | __gthrw(pthread_mutexattr_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:134:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:135:1: error: attribute value 'tune=native' was already specified in 'target' attribute
135 | __gthrw(pthread_mutexattr_settype)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:135:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:136:1: error: attribute value 'tune=native' was already specified in 'target' attribute
136 | __gthrw(pthread_mutexattr_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:136:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:237:10: error: attribute value 'tune=native' was already specified in 'target' attribute
237 | __gthrw2(__gthrw_(__pthread_key_create),
| ^~~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:237:10: error: attribute value 'tune=native' was already specified in 'target' attribute
nafta.cpp: In function 'int main()':
nafta.cpp:117:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | while (first < events.size() && events[first].x <= l) first++;
| ~~~~~~^~~~~~~~~~~~~~~
nafta.cpp:120:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | while (i < events.size() && events[i].x < r) {
| ~~^~~~~~~~~~~~~~~
