| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 815794 |
2023-08-08T23:29:36 Z |
beaboss |
Nafta (COI15_nafta) |
C++14 |
|
362 ms |
114560 KB |
// Source: https://oj.uz/problem/view/COI15_nafta
#include "bits/stdc++.h"
using namespace std;
#define s second
#define f first
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<int> vi;
#define FOR(i, a, b) for (int i = (a); i<b; i++)
const int N = 2001;
int r, s;
int a[N][N];
bool vis[N][N];
vpii events[N];
int st[N];
int miny, maxy, cost;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
int contr[N];
int overlap[N][N];
int dp[N][N];
int ans[N];
void compute(int l, int r, int j, int optl, int optr) {
if (l > r) return;
int i = (l + r) / 2;
int cur_opt;
int best = 0;
for (int k = optl; k <= min(i, optr); k++) {
if (dp[k][j-1] - overlap[k][i] >= best) {
best = dp[k][j-1] - overlap[k][i];
cur_opt = k;
}
}
dp[i][j] = best + contr[i];
ans[j] = max(dp[i][j], ans[j]);
compute(l, i - 1, j, optl, cur_opt);
compute(i+1, r, j, cur_opt, optr);
}
void solve(int x, int y) {
// cout << x << y << endl;
miny = min(miny, y);
maxy = max(maxy, y);
cost += a[x][y];
vis[x][y] = true;
for (int i = 0; i < 4; i++) {
int newx = x + dx[i];
int newy = y + dy[i];
if (newx >= 0 && newx < r && newy >= 0 && newy < s && !vis[newx][newy] && a[newx][newy] != -1) solve(newx, newy);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// input
cin >> r >> s;
FOR(i, 0, r) {
FOR(j, 0, s) {
char inp;
cin >> inp;
if (inp == '.') a[i][j] = -1;
else a[i][j] = inp - '0';
}
}
// extract components
FOR(i, 0, r) FOR(j, 0, s) {
if (!vis[i][j] && a[i][j] != -1) {
maxy = j;
miny = j;
cost = 0;
solve(i, j);
events[miny].pb({miny, cost});
events[maxy+1].pb({miny, -cost});
FOR(i, miny, maxy + 1) {
dp[i][0] += cost;
contr[i] += cost;
ans[0] = max(ans[0],dp[i][0]);
}
}
}
// get overlap
FOR(i, 0, s) {
for (auto val: events[i]) st[val.f] += val.s;
int cur_count = 0;
FOR(j, 0, i + 1) {
cur_count += st[j];
overlap[j][i] = cur_count;
}
}
cout << ans[0] << endl;
FOR(i, 1, s) {
compute(0, s-1, i, 0, s-1);
cout << ans[i] << endl;
}
}
Compilation message
nafta.cpp: In function 'void compute(int, int, int, int, int)':
nafta.cpp:59:9: warning: 'cur_opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
59 | compute(l, i - 1, j, optl, cur_opt);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
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 |
1160 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 |
1108 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 |
1160 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 |
1108 KB |
Output is correct |
| 7 |
Correct |
6 ms |
5908 KB |
Output is correct |
| 8 |
Correct |
8 ms |
5644 KB |
Output is correct |
| 9 |
Correct |
8 ms |
6908 KB |
Output is correct |
| 10 |
Correct |
6 ms |
5716 KB |
Output is correct |
| 11 |
Correct |
5 ms |
5616 KB |
Output is correct |
| 12 |
Correct |
5 ms |
5476 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 |
1160 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 |
1108 KB |
Output is correct |
| 7 |
Correct |
6 ms |
5908 KB |
Output is correct |
| 8 |
Correct |
8 ms |
5644 KB |
Output is correct |
| 9 |
Correct |
8 ms |
6908 KB |
Output is correct |
| 10 |
Correct |
6 ms |
5716 KB |
Output is correct |
| 11 |
Correct |
5 ms |
5616 KB |
Output is correct |
| 12 |
Correct |
5 ms |
5476 KB |
Output is correct |
| 13 |
Correct |
305 ms |
67500 KB |
Output is correct |
| 14 |
Correct |
333 ms |
61060 KB |
Output is correct |
| 15 |
Correct |
362 ms |
114560 KB |
Output is correct |
| 16 |
Correct |
262 ms |
59404 KB |
Output is correct |
| 17 |
Correct |
226 ms |
53744 KB |
Output is correct |
| 18 |
Correct |
228 ms |
53564 KB |
Output is correct |
