#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define MOD 1000000007
/* Date: 10/13/21
* Link: https://oj.uz/problem/view/COI15_nafta
* Verdict: WA
*/
int R, S;
bool visited[2001][2001];
int grid[2001][2001];
LL gain[2001][2001];
vector<pii> delta[2001];
LL column_sum[2001];
LL dp[2001][2001];
void solve(int layer, int solve_start, int solve_end, int check_start, int check_end) {
if (solve_start > solve_end) return;
int mid = (solve_start + solve_end)/2;
LL best_val = -1; int cur_best = -1;
for (int i = check_start; i <= min(mid, check_end); i++) {
LL cur_val = dp[layer-1][i] + gain[i][mid];
if (cur_val > best_val) {
best_val = cur_val; cur_best = i;
}
}
dp[layer][mid] = best_val;
solve(layer, solve_start, mid-1, check_start, cur_best);
solve(layer, mid+1, solve_end, cur_best, check_end);
}
int main() {
ios::sync_with_stdio(0);
cin >> R >> S;
string str;
getline(cin, str);
for (int i = 0; i <= 2000; i++) {
for (int j = 0; j <= 2000; j++) {
visited[i][j] = false;
grid[i][j] = 0;
gain[i][j] = 0;
dp[i][j] = 0;
}
}
for (int i = 0; i <= 2000; i++) {
column_sum[i] = 0;
}
for (int i = 0; i < R; i++) {
getline(cin, str);
for (int j = 0; j < S; j++) {
if (str[j] == '.') {
grid[i][j] = -1;
visited[i][j] = true;
} else {
grid[i][j] = str[j]-'0';
}
}
}
vector<pii> q;
for (int i = 0; i < R; i++) {
for (int j = 0; j < S; j++) {
if (!visited[i][j]) {
LL size = 0;
q.pb(mp(i, j));
visited[i][j] = true;
int minc = j, maxc = j;
while(q.size() > 0) {
pii cur = q.back(); q.pop_back();
int cr = cur.first, cc = cur.second;
size += grid[cr][cc];
minc = min(minc, cc); maxc = max(maxc, cc);
if (cr != 0 && !visited[cr-1][cc]) {
visited[cr-1][cc] = true;
q.pb(mp(cr-1, cc));
}
if (cr != R-1 && !visited[cr+1][cc]) {
visited[cr+1][cc] = true;
q.pb(mp(cr+1, cc));
}
if (cc != 0 && !visited[cr][cc-1]) {
visited[cr][cc-1] = true;
q.pb(mp(cr, cc-1));
}
if (cc != S-1 && !visited[cr][cc+1]) {
visited[cr][cc+1] = true;
q.pb(mp(cr, cc+1));
}
}
for (int column = minc; column <= maxc; column++) {
column_sum[column] += size;
delta[column].pb(mp(maxc, size));
}
}
}
}
for (int i = 0; i < S; i++) sort(delta[i].begin(), delta[i].end());
for (int i = 0; i < S; i++) {
LL remove = column_sum[i];
int delta_ptr = 0;
for (int j = i; j < S; j++) {
gain[i][j] = column_sum[j] - remove;
while(delta_ptr != delta[i].size() && delta[i][delta_ptr].first == j) {
remove -= delta[i][delta_ptr].second;
delta_ptr++;
}
}
}
for (int i = 0; i < S; i++) dp[1][i] = column_sum[i];
for (int i = 2; i <= S; i++) {
solve(i, 0, S-1, 0, S-1);
}
for (int i = 1; i <= S; i++) {
LL cmax = -1;
for (int j = 0; j < S; j++) {
cmax = max(cmax, dp[i][j]);
}
cout << cmax << endl;
}
return 0;
}
Compilation message
nafta.cpp: In function 'int main()':
nafta.cpp:113:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | while(delta_ptr != delta[i].size() && delta[i][delta_ptr].first == j) {
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
82544 KB |
Output is correct |
| 2 |
Correct |
34 ms |
82604 KB |
Output is correct |
| 3 |
Correct |
35 ms |
82536 KB |
Output is correct |
| 4 |
Correct |
32 ms |
82576 KB |
Output is correct |
| 5 |
Correct |
33 ms |
82636 KB |
Output is correct |
| 6 |
Correct |
36 ms |
82616 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
82544 KB |
Output is correct |
| 2 |
Correct |
34 ms |
82604 KB |
Output is correct |
| 3 |
Correct |
35 ms |
82536 KB |
Output is correct |
| 4 |
Correct |
32 ms |
82576 KB |
Output is correct |
| 5 |
Correct |
33 ms |
82636 KB |
Output is correct |
| 6 |
Correct |
36 ms |
82616 KB |
Output is correct |
| 7 |
Correct |
38 ms |
82984 KB |
Output is correct |
| 8 |
Correct |
40 ms |
82820 KB |
Output is correct |
| 9 |
Correct |
36 ms |
82916 KB |
Output is correct |
| 10 |
Correct |
38 ms |
83084 KB |
Output is correct |
| 11 |
Correct |
37 ms |
83020 KB |
Output is correct |
| 12 |
Correct |
37 ms |
83012 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
82544 KB |
Output is correct |
| 2 |
Correct |
34 ms |
82604 KB |
Output is correct |
| 3 |
Correct |
35 ms |
82536 KB |
Output is correct |
| 4 |
Correct |
32 ms |
82576 KB |
Output is correct |
| 5 |
Correct |
33 ms |
82636 KB |
Output is correct |
| 6 |
Correct |
36 ms |
82616 KB |
Output is correct |
| 7 |
Correct |
38 ms |
82984 KB |
Output is correct |
| 8 |
Correct |
40 ms |
82820 KB |
Output is correct |
| 9 |
Correct |
36 ms |
82916 KB |
Output is correct |
| 10 |
Correct |
38 ms |
83084 KB |
Output is correct |
| 11 |
Correct |
37 ms |
83020 KB |
Output is correct |
| 12 |
Correct |
37 ms |
83012 KB |
Output is correct |
| 13 |
Correct |
314 ms |
95428 KB |
Output is correct |
| 14 |
Correct |
358 ms |
95556 KB |
Output is correct |
| 15 |
Correct |
321 ms |
90836 KB |
Output is correct |
| 16 |
Correct |
316 ms |
97860 KB |
Output is correct |
| 17 |
Correct |
361 ms |
98156 KB |
Output is correct |
| 18 |
Correct |
337 ms |
97288 KB |
Output is correct |
