| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 412660 |
2021-05-27T09:41:56 Z |
hgmhc |
Nafta (COI15_nafta) |
C++17 |
|
3 ms |
332 KB |
#include <bits/stdc++.h>
#define REP(i,a,b) for (int i = (a); i <= (b); ++i)
#define PER(i,a,b) for (int i = (b); i >= (a); --i)
#define log2(x) (31-__builtin_clz(x))
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
#define debug(x) cout << #x << " is " << x << endl
#define endl '\n'
using namespace std; using ll = long long; using ii = pair<int,int>; using iii = tuple<int,int,int>;
void solution(); int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("ouput.txt","w",stdout);
#endif
ios::sync_with_stdio(0); cin.tie(0); solution();
}
using ci = complex<int>;
const ci d4[] {{0,1},{1,0},{0,-1},{-1,0}}, d8[] {{0,1},{1,0},{0,-1},{-1,0}, {1,1},{1,-1},{-1,1},{-1,-1}};
#define R real()
#define C imag()
#define P(x) (x).R][(x).C
const int N = 2003;
int n, m, b[N][N], dp[N][N], p[N][N];
bool visited[N][N];
inline int cost(int s, int e) {
return p[e][e]-p[s][e];
}
void compute(int i, ii K, ii J) {
if (J.first > J.second) return;
int z = (J.first+J.second)>>1, p;
dp[i][z] = 0;
REP(k,K.first,K.second) {
if (k >= z) break;
if (int c = cost(k,z); dp[i][z] < dp[i-1][k]+c) {
dp[i][z] = dp[i-1][k]+c;
p = k;
}
}
compute(i,{K.first,p},{J.first,z-1});
compute(i,{p,K.second},{z+1,J.second});
}
bool canGo(ci s) {
return 1 <= s.R && s.R <= n && 1 <= s.C && s.C <= m && b[P(s)] != -1 && !visited[P(s)];}
iii dfs(ci s) {
visited[P(s)] = true;
int o = 0, x = s.C, y = s.C;
for (auto d : d4) if (canGo(s+d)) {
auto [l,r,z] = dfs(s+d);
o += z;
x = min(l,x);
y = max(r,y);
}
return {x,y,o+b[P(s)]};
}
void floodFill() {
REP(i,1,n) REP(j,1,m) {
if (canGo({i,j})) {
auto[l,r,x] = dfs({i,j});
p[l][l] += x; p[r+1][r+1] += x;
p[r+1][l] -= x; p[l][r+1] -= x;
}
}
}
void input() {
cin >> n >> m;
REP(i,1,n) REP(j,1,m) {
char c; cin >> c;
if (c == '.') b[i][j] = -1;
else b[i][j] = c-'0';
}
}
void solution() {
input();
floodFill();
REP(i,1,m) REP(j,1,m) {
p[i][j] += p[i-1][j]+p[i][j-1]-p[i-1][j-1];
}
REP(i,1,m) {
compute(i,{0,m-1},{1,m});
cout << *max_element(dp[i],dp[i]+m+1) << endl;
}
}
Compilation message
nafta.cpp: In function 'int main()':
nafta.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | freopen("input.txt","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
nafta.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | freopen("ouput.txt","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
