# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
980451 |
2024-05-12T07:35:40 Z |
michified |
Nafta (COI15_nafta) |
C++17 |
|
1 ms |
348 KB |
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
using namespace std;
int rs, cs, lb, rb, tot;
vector<vector<int>> grid, dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}, dp;
vector<map<int, pii>> intervsCol;
vector<int> intervsColtot;
vector<vector<bool>> seen;
void getInterv(int curi, int curj) {
seen[curi][curj] = true;
lb = min(lb, curj);
rb = max(rb, curj);
tot += grid[curi][curj];
int nexti, nextj;
for (auto& dir : dirs) {
nexti = curi + dir[0];
nextj = curj + dir[1];
if (nexti >= 0 and nexti < rs and nextj >= 0 and nextj < cs and not seen[nexti][nextj] and grid[nexti][nextj] != -1) getInterv(nexti, nextj);
}
}
void solve(int i, int l, int r, int optl, int optr) {
if (l > r) return;
int mid = (l + r) / 2, opt = optl, k, cur, best = dp[i - 1][optl - 2] + intervsColtot[mid] - intervsCol[mid].lower_bound(optl - 1) -> second.second;
for (k = optl; k <= optr; k++) {
cur = dp[i - 1][k - 1] + intervsColtot[mid] - intervsCol[mid].lower_bound(k) -> second.second;
if (cur > best) {
best = cur;
opt = k;
}
}
dp[i][mid] = best;
solve(i, l, mid - 1, optl, opt);
solve(i, mid + 1, r, opt, optr);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> rs >> cs;
grid.resize(rs, vector<int>(cs));
seen.resize(rs, vector<bool>(cs));
intervsCol.resize(cs);
intervsColtot.resize(cs);
int i, j, k;
string tmp;
for (i = 0; i < rs; i++) {
cin >> tmp;
for (j = 0; j < cs; j++) {
if (tmp[j] == '.') grid[i][j] = -1;
else grid[i][j] = tmp[j] - '0';
}
}
for (i = 0; i < rs; i++) {
for (j = 0; j < cs; j++) {
if (not seen[i][j] and grid[i][j] != -1) {
lb = j;
rb = j;
tot = 0;
getInterv(i, j);
for (k = lb; k <= rb; k++) intervsCol[k][lb].first += tot;
}
}
}
for (i = 0; i < cs; i++) {
auto itr = intervsCol[i].begin();
while (itr != intervsCol[i].end()) {
itr -> second.second = intervsColtot[i];
intervsColtot[i] += itr -> second.first;
itr = next(itr);
}
intervsCol[i][INT_MAX].second = intervsColtot[i];
}
dp.resize(cs + 1, vector<int>(cs));
for (j = 0; j < cs; j++) dp[1][j] = intervsColtot[j];
for (i = 2; i <= cs; i++) {
solve(i, i - 1, cs - 1, i, cs - 1);
}
for (i = 1; i <= cs; i++) cout << *max_element(dp[i].begin(), dp[i].end()) << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |