#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"
typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }
void io() {
#ifdef LOCAL_PROJECT
freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else
/* online submission */
#endif
ios_base::sync_with_stdio(false); cin.tie(NULL);
}
const ll MOD = 1000000007LL;
const ll PRIME = 105943LL;
const ll INF = 1e18;
/************************COI TST2 2015 P2****************************************/
typedef pair<pii, int> seg;
const int MX = 2000;
#define LL first.first
#define RR first.second
#define PP second
int R, C;
char oil[MX][MX];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
seg findseg(int i, int j) {
int total = oil[i][j] - '0', l = j, r = j;
queue<pii> q;
q.push({ i,j });
oil[i][j] = '.';
while (!q.empty()) {
i = q.front().first, j = q.front().second;
q.pop();
FOR(d, 0, 4) {
int ni = i + dx[d], nj = j + dy[d];
if (0 <= ni && ni<R && 0 <= nj && nj<C && oil[ni][nj] != '.') {
total += oil[ni][nj] - '0';
minn(l, nj), maxx(r, nj);
q.push({ ni,nj });
oil[ni][nj] = '.';
}
}
}
return{ { l,r }, total };
}
template<class T, int L> struct Bit {
T bit[L + 1];
Bit() {}
void clr() { memset(bit, 0, sizeof bit); }
void upd(int k, T val) { for (k++; k <= L; k += (k&-k)) bit[k] += val; }
T query(int k) { T temp = 0; for (k++; k > 0; k -= (k&-k)) temp += bit[k]; return temp; }
T query(int l, int r) { return query(r) - query(l - 1); }
};
Bit<int, MX> cnt;
void add(int x, int y, int val) {
cnt.upd(x, val);
cnt.upd(y + 1, -val);
//FORE(i, x, y)
// cnt[i] += val;
}
int query(int x) {
return cnt.query(x);
//return cnt[x];
}
void clear() {
cnt.clr();
//memset(cnt, 0, sizeof cnt);
}
int getMax(v<int> &dp) {
int ret = dp[0];
for (auto x : dp) maxx(ret, x);
return ret;
}
v<int> dp_before, dp_cur;
int W[MX][MX]; // W[i][j]: --j---i- new points
void compute(int l, int r, int optl, int optr) {
///* Brute Force: N^2 */
//FOR(i, 0, optr) {
// // calculate dp_cur[i];
// dp_cur[i] = 0;
// FORE(j, 0, i) maxx(dp_cur[i], dp_before[j] + W[i][j]);
//}
/* NlogN Optimized*/
if (l > r) return;
// compute dp[mid]
int mid = (l + r) >> 1;
pair<int, int> best = { 0,-1 };
// [0, mid-1]
// [optl, optr]
for (int j = max(0, optl); j <= min(mid, optr); j++)
maxx(best, { dp_before[j] + W[mid][j],j });
dp_cur[mid] = best.first;
int opt = best.second;
compute(l, mid - 1, optl, opt);
compute(mid + 1, r, opt, optr);
}
void process(v<seg> &alls, int N) { // [0,N-1]
dp_before.resize(N), dp_cur.resize(N);
// setup W[i][j];
v<int> addE[MX], delE[MX];
FOR(i, 0, alls.size())
addE[alls[i].LL].push_back(i), delE[alls[i].RR].push_back(i);
FOR(i, 0, N) {
for (auto j : addE[i]) add(alls[j].LL, alls[j].RR, alls[j].PP);
dp_cur[i] = query(i);
FORE(j, 0, i) W[i][j] = dp_cur[i] - query(j);
for (auto j : delE[i]) add(alls[j].LL, alls[j].RR, -alls[j].PP);
}
cout << getMax(dp_cur) << "\n";
FORE(k, 2, N) {
swap(dp_cur, dp_before);
compute(0, N - 1, 0, N);
cout << getMax(dp_cur) << "\n";
}
}
int main() {
io();
cin >> R >> C;
FOR(i, 0, R) FOR(j, 0, C) cin >> oil[i][j];
v<seg> alls;
FOR(i, 0, R) FOR(j, 0, C) if (oil[i][j] != '.') alls.push_back(findseg(i, j));
//for (auto s : alls) {
// cout << s.LL << " " << s.RR << " " << s.PP << "\n";
//}
process(alls, C);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
760 KB |
Output is correct |
| 2 |
Correct |
2 ms |
760 KB |
Output is correct |
| 3 |
Correct |
2 ms |
760 KB |
Output is correct |
| 4 |
Correct |
2 ms |
760 KB |
Output is correct |
| 5 |
Correct |
2 ms |
760 KB |
Output is correct |
| 6 |
Correct |
2 ms |
760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
760 KB |
Output is correct |
| 2 |
Correct |
2 ms |
760 KB |
Output is correct |
| 3 |
Correct |
2 ms |
760 KB |
Output is correct |
| 4 |
Correct |
2 ms |
760 KB |
Output is correct |
| 5 |
Correct |
2 ms |
760 KB |
Output is correct |
| 6 |
Correct |
2 ms |
760 KB |
Output is correct |
| 7 |
Correct |
9 ms |
2744 KB |
Output is correct |
| 8 |
Correct |
9 ms |
2680 KB |
Output is correct |
| 9 |
Correct |
17 ms |
2424 KB |
Output is correct |
| 10 |
Correct |
8 ms |
2680 KB |
Output is correct |
| 11 |
Correct |
6 ms |
2552 KB |
Output is correct |
| 12 |
Correct |
6 ms |
2424 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
760 KB |
Output is correct |
| 2 |
Correct |
2 ms |
760 KB |
Output is correct |
| 3 |
Correct |
2 ms |
760 KB |
Output is correct |
| 4 |
Correct |
2 ms |
760 KB |
Output is correct |
| 5 |
Correct |
2 ms |
760 KB |
Output is correct |
| 6 |
Correct |
2 ms |
760 KB |
Output is correct |
| 7 |
Correct |
9 ms |
2744 KB |
Output is correct |
| 8 |
Correct |
9 ms |
2680 KB |
Output is correct |
| 9 |
Correct |
17 ms |
2424 KB |
Output is correct |
| 10 |
Correct |
8 ms |
2680 KB |
Output is correct |
| 11 |
Correct |
6 ms |
2552 KB |
Output is correct |
| 12 |
Correct |
6 ms |
2424 KB |
Output is correct |
| 13 |
Correct |
371 ms |
31240 KB |
Output is correct |
| 14 |
Correct |
323 ms |
29220 KB |
Output is correct |
| 15 |
Correct |
285 ms |
22964 KB |
Output is correct |
| 16 |
Correct |
277 ms |
28388 KB |
Output is correct |
| 17 |
Correct |
200 ms |
22504 KB |
Output is correct |
| 18 |
Correct |
187 ms |
22328 KB |
Output is correct |
