// #pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
template<typename T>
string tostr(const T& value) {
ostringstream oss;
oss << value;
return oss.str();
}
template<typename... Args>
string fstr(const string& format, Args... args) {
string result = format;
size_t pos = 0;
size_t argIndex = 0;
auto replaceArg = [&](const auto& arg) {
pos = result.find("{}", pos);
if (pos != string::npos) {
result.replace(pos, 2, tostr(arg));
++argIndex;
}
};
(replaceArg(args), ...);
return result;
}
/*
* Keeps mint objects modulo MOD constant
*/
// const int MOD = 1e9 + 7;
// struct mint {
// int x;
// mint() { x = 0; }
// mint(int X) { x = X; }
// mint(long long X) { x = ((X % MOD) + MOD) % MOD; }
// mint(unsigned long long X) { x = (X % MOD); }
// mint pow(int k) { mint r = 1, a = *this; while (k) { if (k & 1) r *= a; a *= a; k >>= 1; } return r; }
// mint& operator+=(mint o) { if ((x += o.x) >= MOD) x -= MOD; return *this; }
// mint& operator-=(mint o) { if ((x += MOD - o.x) >= MOD) x -= MOD; return *this; }
// mint& operator*=(mint o) { x = 1ll * x * o.x % MOD; return *this; }
// mint& operator/=(mint o) { return (*this) *= o.pow(MOD - 2); }
// mint operator+(mint o) const { return mint(*this) += o; }
// mint operator-(mint o) const { return mint(*this) -= o; }
// mint operator*(mint o) const { return mint(*this) *= o; }
// mint operator/(mint o) const { return mint(*this) /= o; }
// bool operator<(mint o) const { return x < o.x; }
// friend ostream& operator<<(ostream& os, mint a) { os << a.x; return os; }
// };
/*
* Matrices
* Multiplication
*/
// typedef vector<vector<int>> MAT;
// struct Matrix {
// MAT v;
// Matrix(MAT V) { swap(v, V); }
// Matrix(int a, int b) { v.resize(a, vector<int>(b, 0)); }
// Matrix operator*(const Matrix& o) {
// // assert(v[0].size() == o.v.size());
// Matrix M(v.size(), o.v[0].size());
// for (int i = 0; i < v.size(); i++)
// for (int j = 0; j < o.v[0].size(); j++)
// for (int k = 0; k < (int)v[0].size(); k++)
// M.v[i][j] += v[i][k] * o.v[k][j];
// return M;
// }
// Matrix operator^(int k) {
// if (k&1) return (((*this)*(*this))^(k/2))*(*this);
// else return ((*this)*(*this))^(k/2);
// }
// };
/*
* Segment Tree
* - RANGE QUERY
* - RANGE UPDATE
*/
// template<class T>
// T identity; // [SET IDENTITY OF CLASS T, hardcode T classname]
// struct ND {
// ND* ch[2] = { nullptr, nullptr };
// T v, f;
// inline void create() {
// if (!ch[0]) ch[0] = new ND; // [POTENTIALLY UPDATE VALUES]
// if (!ch[1]) ch[1] = new ND; // [POTENTIALLY UPDATE VALUES]
// }
// inline void merge(int l, int r) {
// // [INSERT CODE FOR MERGE SEGMENT]
// }
// inline void push(int l, int r) {
// create();
// // [INSERT CODE FOR PUSHING SEGMENT FLAG]
// }
// void upd(int l, int r, int L, int R, T K) {
// push(l, r);
// if (R < l || r < L) return;
// if (L <= l && r <= R) {
// // [INSERT CODE FOR UPDATE SEGMENT]
// return;
// }
// int m = (l + r) >> 1;
// ch[0]->upd(l, m, L, R, K);
// ch[1]->upd(m+1, r, L, R, K);
// merge(l, r);
// }
// T qry(int l, int r, int L, int R) {
// push(l, r);
// if (R < l || r < L) return identity;
// if (L <= l && r <= R) return s;
// int m = (l + r) >> 1;
// return merge(ch[0]->qry(l,m,L,R), ch[1]->qry(m+1,r,L,R));
// }
// ~ND() { delete ch[0]; delete ch[1]; ch[0] = ch[1] = nullptr; }
// };
/*
* Convex Hull Trick
* - ORDERED SLOPES
* - UNORDERED QUERIES O(N log N), ORDERED QUERIES O(N)
*/
// struct F {
// int a, b;
// F() {}
// F(int A, int B) : a(A), b(B){ if (b<0) a*=-1, b*=-1; }
// bool operator<(F o) const { return a*o.b < b*o.a; }
// bool operator<=(F o) const { return a*o.b <= b*o.a; }
// };
// struct L {
// int m, b;
// int operator()(int x) { return m*x + b; }
// F operator^(L o) { return F{b-o.b,o.m-m}; }
// };
// struct CHT {
// vector<L> h;
// // deque<L> h; // if using SECOND CODE in QRY FUNCTION
// void add(L l) {
// // // min hull + decreasing slopes OR max hull + increasing slopes
// // while (h.size() >= 2 && (h.end()[-2]^l) <= (h.end()[-2]^h.back())) h.pop_back();
// // h.push_back(l);
// // // min hull + increasing slopes OR max hull + decreasing slopes
// // while (h.size() >= 2 && (h.end()[-2]^h.back()) <= (h.end()[-2]^l)) h.pop_back();
// // h.push_back(l);
// }
// int qry(int x) {
// // O(N log N) time, unordered queries
// // int lo = 0, hi = h.size()-1;
// // while (lo < hi) {
// // int m = (lo + hi) >> 1;
// // if (h[m](x) < h[m+1](x)) // < or > depending on min/max qry
// // lo = m+1;
// // else
// // hi = m;
// // }
// // return h[lo](x);
// // if need O(N) time, use **DEQUE INSTEAD OF VECTOR** & use code below
// // while (h.size() >= 2 && h[1](x) < h[0](x)) h.pop_front(); // < or > depending on min/max qry
// // return h[0](x);
// }
// };
/*
* Li Chao Tree
* UNORDERED SLOPES, UNORDERED QUERIES O(N log N)
* Extension of segment tree
*/
// struct F {
// int a, b;
// F() {}
// F(int A, int B) : a(A), b(B){ if (b<0) a*=-1, b*=-1; }
// bool operator<(F o) const { return a*o.b < b*o.a; }
// bool operator<=(F o) const { return a*o.b <= b*o.a; }
// };
// struct L {
// int m, b;
// int operator()(int x) { return m*x + b; }
// F operator^(L o) { return F{b-o.b,o.m-m}; }
// };
// // #define OP(a, b) (a < b) // DEFINE OPERATOR
// // #define OPR(a, b) (min(a,b)) // DEFINE OPERATOR
// #define OP(a, b) (a > b)
// #define OPR(a, b) (max(a,b))
// struct ND {
// ND * ch[2] = { nullptr, nullptr };
// L v = L{1, 0};
// void create() {
// if (!ch[0]) { ch[0] = new ND; ch[0]->v = v; }
// if (!ch[1]) { ch[1] = new ND; ch[1]->v = v; }
// }
// void upd(int l, int r, L V) {
// // update the li chao tree with line V
// if (v.m == V.m && v.b == V.b) return;
// if (l == r) {
// // if new line is better, swap
// if (OP(V(l), v(l))) swap(V, v);
// return;
// }
// create();
// int m = (l + r) >> 1; // midpoint
// if (OP(V(m), v(m))) swap(V, v); // if new line is better at mid, it has one half, so swap
// F x = v ^ V; // intersection of two lines
// if (x <= F(m, 1))
// ch[0]->upd(l, m, V);
// else
// ch[1]->upd(m+1, r, V);
// }
// int qry(int l, int r, int X) {
// // qry li chao tree for x coord X
// int ret = v(X); // gets value for current segment
// if (l != r) {
// int m = (l + r) >> 1;
// if (X <= m && ch[0] != nullptr) return OPR(ret, ch[0]->qry(l, m, X));
// if (X > m && ch[1] != nullptr) return OPR(ret, ch[1]->qry(m+1, r, X));
// }
// return ret;
// }
// };
// #undef OP
// #undef OPR
/*
* Heavy Light Decomp
*/
#define valid(a, b) (a >= 1 && b >= 1 && a <= r && b <= s)
const int maxr = 2005;
int r, s;
int gr[maxr][maxr];
int dp[maxr][maxr], f[maxr][maxr], g[maxr][maxr];
int dr[] = {1, 0, -1, 0};
int dc[] = {0, 1, 0, -1};
pair<int,int> curc;
int num;
void ff(int R, int C) {
num += gr[R][C]; gr[R][C] = -1;
curc.first = min(curc.first, C), curc.second = max(curc.second, C);
for (int i = 0; i < 4; i++) {
int nr = R + dr[i], nc = C + dc[i];
if (!valid(nr, nc)) continue;
if (gr[nr][nc] == -1) continue;
ff(nr, nc);
}
}
void dvc(int L, int R, int lh, int hh, int k) {
if (L > R) return;
// cout << "-----" << endl;
int m = (L + R) >> 1;
// for (int i = lh; i <= min(m, hh); i++)
// cout << L << ' ' << R << ' ' << m << ' ' << i << ' ' << dp[i][k-1] + f[i][m] << endl;
int j = lh;
for (int i = lh; i <= min(m, hh); i++)
if (dp[m][k] <= dp[i][k-1] + f[i][m])
dp[m][k] = dp[i][k-1] + f[i][m], j = i;
if (L == R) return;
dvc(L, m-1, lh, j, k);
dvc(m+1, R, j, hh, k);
}
void solve() {
cin >> r >> s;
for (int i = 1; i <= r; i++)
for (int j = 1; j <= s; j++) {
char c; cin >> c;
if (c == '.') gr[i][j] = -1;
else gr[i][j] = c - '0';
}
for (int i = 1; i <= r; i++)
for (int j = 1; j <= s; j++) {
if (gr[i][j] == -1) continue;
curc = {j, j}; num = 0;
ff(i, j);
for (int k = curc.first; k <= curc.second; k++)
g[curc.first][k] += num;
}
for (int j = s; j >= 1; j--) // loop over js
for (int i = j-1; i >= 0; i--) // loop over is stemming away from cur j
f[i][j] = f[i+1][j] + g[i+1][j];
// for (int i = 0; i <= s; i++) {
// for (int j = 0; j <= s; j++) {
// cout << g[i][j] << ' ';
// }
// cout << endl;
// }
// cout << endl;
// for (int i = 0; i <= s; i++) {
// for (int j = 0; j <= s; j++) {
// cout << f[i][j] << ' ';
// }
// cout << endl;
// }
// cout << endl;
for (int k = 1; k <= s; k++)
dvc(1, s, 0, s, k);
for (int i = 1; i <= s; i++) {
int r = 0;
for (int j = 1; j <= s; j++)
r = max(dp[j][i], r);
cout << r << endl;
}
return;
}
signed main() {
cin.tie(nullptr) -> ios::sync_with_stdio(false);
// freopen("main.in", "r", stdin);
int t;
// cin >> t;
t=1;
while(t--) solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 3 |
Correct |
1 ms |
980 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 6 |
Correct |
1 ms |
980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 3 |
Correct |
1 ms |
980 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 6 |
Correct |
1 ms |
980 KB |
Output is correct |
| 7 |
Correct |
6 ms |
6100 KB |
Output is correct |
| 8 |
Correct |
7 ms |
6076 KB |
Output is correct |
| 9 |
Correct |
7 ms |
7508 KB |
Output is correct |
| 10 |
Correct |
6 ms |
6100 KB |
Output is correct |
| 11 |
Correct |
5 ms |
5972 KB |
Output is correct |
| 12 |
Correct |
5 ms |
5460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 3 |
Correct |
1 ms |
980 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 6 |
Correct |
1 ms |
980 KB |
Output is correct |
| 7 |
Correct |
6 ms |
6100 KB |
Output is correct |
| 8 |
Correct |
7 ms |
6076 KB |
Output is correct |
| 9 |
Correct |
7 ms |
7508 KB |
Output is correct |
| 10 |
Correct |
6 ms |
6100 KB |
Output is correct |
| 11 |
Correct |
5 ms |
5972 KB |
Output is correct |
| 12 |
Correct |
5 ms |
5460 KB |
Output is correct |
| 13 |
Correct |
270 ms |
57496 KB |
Output is correct |
| 14 |
Correct |
286 ms |
57548 KB |
Output is correct |
| 15 |
Correct |
334 ms |
123656 KB |
Output is correct |
| 16 |
Correct |
247 ms |
57448 KB |
Output is correct |
| 17 |
Correct |
238 ms |
54968 KB |
Output is correct |
| 18 |
Correct |
245 ms |
53316 KB |
Output is correct |
