| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 844851 |
2023-09-06T04:43:16 Z |
Cookie |
Nafta (COI15_nafta) |
C++14 |
|
1 ms |
4952 KB |
#include<bits/stdc++.h>
#define ll long long
#define vt vector
#define pb push_back
#define pii pair<int, int>
#define sz(v) (int)v.size()
using namespace std;
const ll base = 107, mod = 1e9 + 7;
const int mxn = 2005, inf = 1e9, sq = 400;
const int X[4] = {1, -1, 0, 0};
const int Y[4] = {0, 0, 1, -1};
struct BIT{
ll bit[mxn + 1];
void upd(int p, ll v){
while(p <= mxn){
bit[p] += v; p += p & (-p);
}
}
ll get(int p){
ll ans = 0;
while(p){
ans += bit[p]; p -= p & (-p);
}
return(ans);
}
ll query(int l, int r){
if(l > r)return(0);
return(get(r) - get(l - 1));
}
int kth(ll x){
ll sm = 0, id = 0;
for(int i = 18; i >= 0; i--){
if(id + (1 << i) <= mxn && sm + bit[id + (1 << i)] < x){
id += (1 << i); sm += bit[id];
}
}
return(id + 1);
}
};
BIT bit;
int n, m;
int sm = 0, mn, mx;
bool vis[2005][2005];
char c[2005][2005];
int cost[2005][2005], dp[2005][2005];
bool inside(int nwx, int nwy){
return(nwx >= 1 && nwx <= n && nwy >= 1 && nwy <= m);
}
void dfs(int x, int y){
mn = min(mn, y); mx = max(mx, y);
vis[x][y] = 1; sm += (c[x][y] - '0');
for(int i = 0; i < 4; i++){
int nwx = x + X[i], nwy = y + Y[i];
if(inside(nwx, nwy) && c[nwx][nwy] != '.' && !vis[nwx][nwy]){
dfs(nwx, nwy);
}
}
}
void solve(int id, int l, int r, int bestl, int bestr){
if(l > r)return;
int mid = (l + r) >> 1;
int &mx = dp[id][mid], idd = -1;
for(int i = bestl; i <= min(r - 1, bestr); i++){
int cand = dp[id - 1][i] + cost[mid][i];
if(cand > mx){
mx = cand; idd = i;
}
}
solve(id, l, mid - 1, bestl, idd); solve(id, mid + 1, r, idd, bestr);
}
struct E{
int l, r, v;
};
vt<E>events[mxn + 1];
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> c[i][j];
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(c[i][j] != '.' && !vis[i][j]){
sm = 0; mn = mx = j;
dfs(i, j);
events[mn].pb({mn, mx, sm}); events[mx + 1].pb({mn, mx, -sm});
}
}
}
for(int i = 1; i <= m; i++){
for(auto [l, r, v]: events[i]){
bit.upd(l, v); bit.upd(r + 1, -v);
}
for(int j = i - 1; j >= 0; j--){
cost[i][j] = bit.get(i) - bit.get(j);
}
}
for(int i = 1; i <= m; i++){
dp[1][i] = cost[i][0];
}
cout << *max_element(dp[1] + 1, dp[1] + m + 1) << "\n";
for(int i = 2; i <= m; i++){
solve(i, i, m, i - 1, m);
cout << *max_element(dp[i] + 1, dp[i] + m + 1) << "\n";
}
}
Compilation message
nafta.cpp: In function 'int main()':
nafta.cpp:97:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
97 | for(auto [l, r, v]: events[i]){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
