| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 495626 |
2021-12-19T15:27:40 Z |
Dirii |
Nafta (COI15_nafta) |
C++14 |
|
419 ms |
105744 KB |
// #pragma GCC target("avx2")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define cll const ll
#define lp(a, b, c) for(ll a = b; a <= c; ++a)
#define lpd(a, b, c) for(ll a = b; a >= c; --a)
#define vec(a) vector<a>
#define pp(a, b) pair<a, b>
#define EACHCASE lpd(cs, read(), 1)
#define Fname "f"
using namespace std;
template <typename T> inline void Read(T &x){
x = 0; char c;
ll dau = 1;
while(!isdigit(c = getchar())) if(c == '-') dau = -1;
do{
x = x * 10 + c - '0';
} while (isdigit(c = getchar()));
x *= dau;
}
ll read(){
ll tmp;
cin >> tmp;
return tmp;
}
void giuncute(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
}
void OF(){
if(fopen(Fname".inp", "r")){
freopen(Fname".inp", "r", stdin);
freopen(Fname".out", "w", stdout);
} else if(fopen(Fname".in", "r")){
freopen(Fname".in", "r", stdin);
freopen(Fname".out", "w", stdout);
}
}
cll mxn = 2e3 + 4, dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
ll n, m, a[mxn][mxn], cost[mxn][mxn] = {{0}}, dp[mxn][mxn] = {{0}};
vec(pp(pp(ll, ll), ll)) range;
bool d[mxn][mxn] = {{0}};
void sol(ll k, ll l, ll r, ll optL, ll optR){
if(l > r) return;
ll mid = (l + r) >> 1, optMid = -1;
lp(i, optL, min(optR, mid)) if(dp[k - 1][i - 1] + cost[i][mid] > dp[k][mid]){
dp[k][mid] = dp[k - 1][i - 1] + cost[i][mid],
optMid = i;
}
sol(k, l, mid - 1, optL, optMid);
sol(k, mid + 1, r, optMid, optR);
}
int main(){
giuncute();
#ifndef ONLINE_JUDGE
OF();
#endif
cin >> n >> m;
lp(i, 1, n) lp(j, 1, m){
char c;
cin >> c;
if(c == '.') a[i][j] = -1;
else a[i][j] = c - '0';
}
lp(i, 0, max(n, m) + 1) a[i][0] = a[0][i] = a[n + 1][i] = a[i][m + 1] = -1;
lp(i, 1, n) lp(j, 1, m) if(~a[i][j] && !d[i][j]){
// bfs
queue<pp(ll, ll)> q;
ll val = a[i][j];
pp(ll, ll) res = {j, j};
d[i][j] = 1;
q.push({i, j});
while(q.size()){
ll u = q.front().first, v = q.front().second;
q.pop();
lp(i, 0, 3){
ll nu = u + dx[i], nv = v + dy[i];
if(~a[nu][nv] && !d[nu][nv]){
d[nu][nv] = 1;
val += a[nu][nv];
res.first = min(res.first, nv);
res.second = max(res.second, nv);
q.push({nu, nv});
}
}
}
range.push_back({res, val});
}
sort(range.begin(), range.end(), [](pp(pp(ll, ll), ll) &x, pp(pp(ll, ll), ll) &y){
return x.first.second < y.first.second;
});
ll cur = -1;
lp(_right, 1, m){
while(cur < (ll)range.size() - 1 && range[cur + 1].first.second <= _right)
++cur,
cost[range[cur].first.first][_right] += range[cur].second;
lp(i, 1, _right)
cost[i][_right] += cost[i - 1][_right] + cost[i][_right - 1] - cost[i - 1][_right - 1],
dp[1][_right] = max(dp[1][_right], cost[i][_right]);
}
lp(i, 2, m) sol(i, 1, m, 1, m);
lp(i, 1, m) cout << dp[i][m] << '\n';
}
Compilation message
nafta.cpp: In function 'void OF()':
nafta.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | freopen(Fname".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
nafta.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
39 | freopen(Fname".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
nafta.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | freopen(Fname".in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
nafta.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | freopen(Fname".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1104 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 3 |
Correct |
1 ms |
968 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1104 KB |
Output is correct |
| 5 |
Correct |
1 ms |
976 KB |
Output is correct |
| 6 |
Correct |
1 ms |
976 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1104 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 3 |
Correct |
1 ms |
968 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1104 KB |
Output is correct |
| 5 |
Correct |
1 ms |
976 KB |
Output is correct |
| 6 |
Correct |
1 ms |
976 KB |
Output is correct |
| 7 |
Correct |
9 ms |
6736 KB |
Output is correct |
| 8 |
Correct |
11 ms |
6612 KB |
Output is correct |
| 9 |
Correct |
10 ms |
6356 KB |
Output is correct |
| 10 |
Correct |
9 ms |
6676 KB |
Output is correct |
| 11 |
Correct |
9 ms |
6500 KB |
Output is correct |
| 12 |
Correct |
8 ms |
6352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1104 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 3 |
Correct |
1 ms |
968 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1104 KB |
Output is correct |
| 5 |
Correct |
1 ms |
976 KB |
Output is correct |
| 6 |
Correct |
1 ms |
976 KB |
Output is correct |
| 7 |
Correct |
9 ms |
6736 KB |
Output is correct |
| 8 |
Correct |
11 ms |
6612 KB |
Output is correct |
| 9 |
Correct |
10 ms |
6356 KB |
Output is correct |
| 10 |
Correct |
9 ms |
6676 KB |
Output is correct |
| 11 |
Correct |
9 ms |
6500 KB |
Output is correct |
| 12 |
Correct |
8 ms |
6352 KB |
Output is correct |
| 13 |
Correct |
352 ms |
105744 KB |
Output is correct |
| 14 |
Correct |
419 ms |
99932 KB |
Output is correct |
| 15 |
Correct |
377 ms |
94372 KB |
Output is correct |
| 16 |
Correct |
280 ms |
99688 KB |
Output is correct |
| 17 |
Correct |
325 ms |
94112 KB |
Output is correct |
| 18 |
Correct |
282 ms |
93900 KB |
Output is correct |
