| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 704816 |
2023-03-03T04:22:39 Z |
kelfert |
Nafta (COI15_nafta) |
C++17 |
|
1000 ms |
59276 KB |
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <iomanip>
#include <queue>
#include <stack>
#include <random>
#include <chrono>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
typedef long long ll;
mt19937 rnd(std::chrono::duration_cast<std::chrono::milliseconds>
(std::chrono::system_clock::now().time_since_epoch()).count());
const ll MOD = 1e9 + 7;
const int INF = 2e9;
const int N = 2010;
int cost[N][N], used[N][N], a[N][N];
vector<vector<int> > dp;
void divide(int j, int l, int r, int ql, int qr) {
if (l >= r) return;
int m = (l + r) / 2;
int opt;
for (int i = ql; i < min(m, qr); i++) {
if (dp[j][m] < dp[j - 1][i] + cost[i][m]) {
dp[j][m] = dp[j - 1][i] + cost[i][m];
opt = i;
}
}
//cout << j << " " << m << " " << dp[j][m] << "\n";
divide(j, l, m, ql, opt + 1);
divide(j, m + 1, r, opt, qr);
}
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
void dfs(int vx, int vy, int &sum, int &l, int &r) {
used[vx][vy] = 1;
sum += a[vx][vy];
l = min(l, vy);
r = max(r, vy);
for (int k = 0; k < 4; k++) {
int x = vx + dx[k], y = vy + dy[k];
if (!used[x][y] && a[x][y] != -1) {
dfs(x, y, sum, l, r);
}
}
}
const int OPEN = 1;
const int CLOSE = -1;
struct Seg {
int l, r, sum;
Seg(int l, int r, int sum) : l(l), r(r), sum(sum) {}
Seg() {}
};
struct Event {
int x, id, tp, sum;
Event(int x, int id, int tp, int sum) : x(x), id(id), tp(tp), sum(sum) {}
Event() {}
};
bool comp(Event a, Event b) {
return a.x < b.x;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m; cin >> n >> m;
for (int i = 0; i <= n + 1; i++)
for (int j = 0; j <= m + 1; j++)
a[i][j] = -1;
for (int i = 1; i <= n; i++) {
string s; cin >> s;
for (int j = 0; j < m; j++) {
if (s[j] != '.') a[i][j + 1] = (s[j] - '0');
}
}
vector<Seg> seg;
vector<Event> events;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (!used[i][j] && a[i][j] != -1) {
int sum = 0, l = j, r = j;
dfs(i, j, sum, l, r);
seg.pb(Seg(l, r, sum));
events.pb(Event(l, seg.size() - 1, OPEN, sum));
events.pb(Event(r, seg.size() - 1, CLOSE, sum));
}
}
}
sort(all(events), comp);
vector<int> cnt2(m + 1);
for (auto x : events) {
if (x.tp == OPEN) cnt2[x.x] += x.sum;
}
int first = 0;
for (int l = 0; l <= m; l++) {
while (first < events.size() && events[first].x <= l) first++;
int i = first, sum = 0;
//cout << l << " " << first << endl;
for (int r = l; r <= m; r++) {
//cout << " " << r << endl;
while (i < events.size() && events[i].x < r) {
//cout << " " << i << " " << events[i].x << " " << events[i].sum << endl;
if (events[i].tp == OPEN) {
sum += events[i].sum;
} else {
if (seg[events[i].id].l > l) sum -= events[i].sum;
}
i++;
}
cost[l][r] = sum + cnt2[r];
if (l == r) cost[l][r] = 0;
//cout << " " << l << " " << r << " " << cost[l][r] << endl;
}
}
dp.resize(m + 1, vector<int> (m + 1, -INF));
dp[0][0] = 0;
for (int j = 1; j <= m; j++) {
divide(j, 0, m + 1, 0, m + 1);
int ans = 0;
for (int i = 1; i <= m; i++) ans = max(ans, dp[j][i]);
cout << ans << "\n";
}
return 0;
}
Compilation message
nafta.cpp: In function 'int main()':
nafta.cpp:121:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | while (first < events.size() && events[first].x <= l) first++;
| ~~~~~~^~~~~~~~~~~~~~~
nafta.cpp:126:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | while (i < events.size() && events[i].x < r) {
| ~~^~~~~~~~~~~~~~~
nafta.cpp: In function 'void divide(int, int, int, int, int)':
nafta.cpp:49:11: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
49 | divide(j, l, m, ql, opt + 1);
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
980 KB |
Output is correct |
| 2 |
Correct |
1 ms |
980 KB |
Output is correct |
| 3 |
Correct |
1 ms |
980 KB |
Output is correct |
| 4 |
Correct |
1 ms |
852 KB |
Output is correct |
| 5 |
Correct |
1 ms |
852 KB |
Output is correct |
| 6 |
Correct |
1 ms |
852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
980 KB |
Output is correct |
| 2 |
Correct |
1 ms |
980 KB |
Output is correct |
| 3 |
Correct |
1 ms |
980 KB |
Output is correct |
| 4 |
Correct |
1 ms |
852 KB |
Output is correct |
| 5 |
Correct |
1 ms |
852 KB |
Output is correct |
| 6 |
Correct |
1 ms |
852 KB |
Output is correct |
| 7 |
Correct |
22 ms |
5800 KB |
Output is correct |
| 8 |
Correct |
15 ms |
5512 KB |
Output is correct |
| 9 |
Correct |
11 ms |
7256 KB |
Output is correct |
| 10 |
Correct |
15 ms |
4812 KB |
Output is correct |
| 11 |
Correct |
8 ms |
4564 KB |
Output is correct |
| 12 |
Correct |
5 ms |
4564 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
980 KB |
Output is correct |
| 2 |
Correct |
1 ms |
980 KB |
Output is correct |
| 3 |
Correct |
1 ms |
980 KB |
Output is correct |
| 4 |
Correct |
1 ms |
852 KB |
Output is correct |
| 5 |
Correct |
1 ms |
852 KB |
Output is correct |
| 6 |
Correct |
1 ms |
852 KB |
Output is correct |
| 7 |
Correct |
22 ms |
5800 KB |
Output is correct |
| 8 |
Correct |
15 ms |
5512 KB |
Output is correct |
| 9 |
Correct |
11 ms |
7256 KB |
Output is correct |
| 10 |
Correct |
15 ms |
4812 KB |
Output is correct |
| 11 |
Correct |
8 ms |
4564 KB |
Output is correct |
| 12 |
Correct |
5 ms |
4564 KB |
Output is correct |
| 13 |
Execution timed out |
1062 ms |
59276 KB |
Time limit exceeded |
| 14 |
Halted |
0 ms |
0 KB |
- |
