| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 375790 |
2021-03-10T02:07:20 Z |
8e7 |
Nafta (COI15_nafta) |
C++14 |
|
1 ms |
748 KB |
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
#include <set>
#define ll long long
#define maxn 2005
#define pii pair<int, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
int n, m;
int dir[4][2] = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
char a[maxn][maxn];
int dp[2][maxn], w[maxn][maxn];
bool found[maxn][maxn];
int lef, rig, cur;
void dfs(int x, int y) {
lef = min(lef, y);
rig = max(rig, y);
found[x][y] = 1;
cur += a[x][y] - '0';
for (int k = 0;k < 4;k++) {
int nx = x + dir[k][0], ny = y + dir[k][1];
if (nx > 0 && nx <= n && ny > 0 && ny <= m) {
if (a[nx][ny] != '.' && !found[nx][ny]) {
dfs(nx, ny);
}
}
}
}
void solve(int l, int r, int ql, int qr) { //[l, r), [ql, qr)
if (r <= l || qr <= ql) return;
if (qr - ql == 1) {
for (int i = l;i < r;i++) {
dp[1][i] = dp[0][ql] + w[ql + 1][i] - w[i + 1][i + 1];
}
return;
}
int mid = (l + r) / 2;
int ind = ql;
for (int i = ql;i < min(mid, qr);i++) {
int val = dp[0][i] + w[i + 1][mid] - w[mid + 1][mid + 1];
if (val > dp[1][mid]) {
dp[1][mid] = val, ind = i;
}
}
solve(l, mid, ql, ind + 1);
solve(mid + 1, r, ind, qr);
}
int main() {
io
cin >> n >> m;
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= m;j++) cin >> a[i][j];
}
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= m;j++) {
if (!found[i][j] && a[i][j] != '.') {
lef = 1<<30, rig = -1, cur = 0;
dfs(i, j);
//cout << lef << " " << rig << " " << cur << endl;
w[lef][rig] = cur;
}
}
}
for (int i = m;i >= 0;i--) {
for (int j = m;j >= 0;j--) w[i][j] += w[i][j + 1];
if (i < m) {
for (int j = 0;j <= m;j++) w[i][j] += w[i + 1][j];
}
}
for (int i = 0;i <= m;i++) {
for (int j = 0;j < i;j++) w[i][j] = -(1<<30);
}
for (int i = 1;i <= m;i++) {
int ans = 0;
if (i > 1) {
for (int j = i;j <= m;j++) {
for (int k = i - 1;k < j;k++) dp[1][j] = max(dp[1][j], dp[0][k] + w[k + 1][j] - w[j + 1][j + 1]);
}
//solve(i, m + 1, i - 1, m + 1);
}
else {
for (int j = 1;j <= m;j++) dp[1][j] = w[0][j] - w[j + 1][j + 1];
}
for (int j = i;j <= m;j++) {
ans = max(ans, dp[1][j]);
//cout << dp[1][j] << " ";
}
//cout << endl;
for (int j = i;j <= m;j++) dp[0][j] = dp[1][j], dp[1][j] = 0;
cout << ans << "\n";
}
}
/*
w[i][j] is sum of every segment with l >= i, r >= j;
5 5
...3.
....1
..0.3
489..
.....
3 5
999.1
.....
1.999
5 5
.27..
7.063
....7
78...
8...2
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
