| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1061762 |
2024-08-16T12:55:16 Z |
Matthewwww |
Nafta (COI15_nafta) |
C++17 |
|
3 ms |
3676 KB |
bool DEBUG
#ifdef LOCAL
= true;
#include <bits/stdc++.h>
#include <atcoder/all>
#include <local/debug>
#define nyoom 69
#define freopen(...) 69
#else
;
#include <bits/stdc++.h>
#define debug(x) x
#define dbg(x, y) x
#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx2")
#define nyoom ios_base::sync_with_stdio(false); cin.tie(nullptr)
#endif
#ifdef ATCODER
#include <atcoder/all>
using namespace atcoder;
#endif
#define int long long
#define all(x) x.begin(), x.end()
#define err if (DEBUG) cout
#define f first
#define s second
using namespace std;
const int dir[5] = {0, 1, 0, -1, 0};
int n, m;
int stuff[2001][2001];
#define eval(x, y) (~x.first ? x.second - stuff[x.first][y] : 0ll)
struct Clm{
int tl, tm, tr;
pair<pair<int, int>, int> f; // left point then constant
Clm *lft = nullptr, *rht = nullptr;
Clm (int l, int r, pair<pair<int, int>, int> a): tl(l), tr(r), f(a), tm(l+r>>1){}
void update (pair<pair<int, int>, int> nw){
if (eval(nw.f, tm) > eval(f.f, tm))
swap(nw, f);
if (tl+1 == tr)
return;
if (nw.f.f > f.f.f){
if (!rht)
rht = new Clm(tl, tm, nw);
else
rht->update(nw);
} else {
if (!lft)
lft = new Clm(tm, tr, nw);
else
lft->update(nw);
}
}
pair<int, int> query (int x){
if (x < tm)
return lft ? max(lft->query(x), {eval(f.f, x), f.s}) : make_pair(eval(f.f, x), f.s);
return rht ? max(rht->query(x), {eval(f.f, x), f.s}) : make_pair(eval(f.f, x), f.s);
}
};
struct Sgt{
int tl, tr, val = 0;
Sgt *lft, *rht;
Sgt (int l, int r): tl(l), tr(r){
if (tl != tr-1){
int tm = tl+tr>>1;
lft = new Sgt(tl, tm);
rht = new Sgt(tm, tr);
}
}
void update (int i, int x){
if (tl == tr-1){
val += x;
return;
}
(i < lft->tr ? lft : rht)->update(i, x);
val = lft->val+rht->val;
}
int query (int l){
if (l >= tr)
return 0;
if (l <= tl)
return val;
return lft->query(l)+rht->query(l);
}
};
void dfs (int i, int j, vector<vector<int>> &grid, vector<pair<pair<int, int>, int>> &loose){
if (i < 0 || j < 0 || i >= n || j >= m || grid[i][j] == '.'-'0')
return;
loose.back().s += grid[i][j];
grid[i][j] = '.'-'0';
loose.back().f.s = max(loose.back().f.s, j);
loose.back().f.f = min(loose.back().f.f, j);
for (int k = 0; k < 4; k++)
dfs(i+dir[k], j+dir[k+1], grid, loose);
}
int active[2001];
pair<int, int> solve (int punish){
Clm lct(0, m, {{-1, 0}, 0});
pair<int, int> dp[m];
for (int i = 0; i < m; i++){
auto res = lct.query(i);
dp[i].f = res.f+active[i]-punish;
dp[i].s = res.s-1;
lct.update({{i, dp[i].f}, dp[i].s});
}
pair<int, int> best = {0, 0};
for (auto i : dp)
best = max(best, {i.f-i.s*punish, i.s});
dbg(dp, m);
return {best.f, -best.s};
}
signed main(){
nyoom;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m));
vector<pair<pair<int, int>, int>> ranges;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
char a;
cin >> a;
grid[i][j] = a-'0';
}
}
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
if (grid[i][j] != '.'-'0'){
ranges.push_back({{INT_MAX, INT_MIN}, 0});
dfs(i, j, grid, ranges);
}
}
}
sort(ranges.begin(), ranges.end());
int ptr = 0;
for (auto i : ranges){
active[i.f.f] += i.s;
active[i.f.s+1] -= i.s;
}
dbg(active, m+1);
for (int i = 0; i < m; i++)
active[i+1] += active[i];
Sgt sgt(0, m);
for (int i = 0; i < m; i++){
while (ptr < ranges.size() && ranges[ptr].f.f == i){
sgt.update(ranges[ptr].f.s, ranges[ptr].s);
++ptr;
}
for (int j = i; j < m; j++)
stuff[i][j] = sgt.query(j);
for (int j = 0; j < i; j++)
stuff[i][j] = INT_MAX;
}
debug(solve(2));
debug(ranges);
dbg(active, m);
for (int i = 0; i < m; i++){
for (int j = 0; j < m; j++)
err << stuff[i][j] << " ";
err << "\n";
}
for (int i = 1; i <= m; i++){
int ans = -1;
for (int k = 25; k--;)
if (solve(ans+(1<<k)).s > i)
ans += (1<<k);
cout << solve(ans+1).f << "\n";
}
}
#undef int
#undef all
#undef err
#undef f
#undef s
/*
*
* ┏┓ ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃ ━ ┃ ++ + + +
* ████━████+
* ◥██◤ ◥██◤ +
* ┃ ┻ ┃
* ┗━┓ ┏━┛ + +
* ┃ ┃ + + + +Code is far away from
* ┃ ┃ + bug with the llama protecting
* ┃ ┗━━━┓ 神兽保佑,代码无bug
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛ + + + +
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛+ + + +
*/
//thanks cindy
Compilation message
nafta.cpp: In constructor 'Clm::Clm(long long int, long long int, std::pair<std::pair<long long int, long long int>, long long int>)':
nafta.cpp:41:75: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
41 | Clm (int l, int r, pair<pair<int, int>, int> a): tl(l), tr(r), f(a), tm(l+r>>1){}
| ~^~
nafta.cpp:25:11: warning: 'Clm::first' will be initialized after [-Wreorder]
25 | #define f first
| ^~~~~
nafta.cpp:39:28: note: in expansion of macro 'f'
39 | pair<pair<int, int>, int> f; // left point then constant
| ^
nafta.cpp:38:10: warning: 'long long int Clm::tm' [-Wreorder]
38 | int tl, tm, tr;
| ^~
nafta.cpp:41:2: warning: when initialized here [-Wreorder]
41 | Clm (int l, int r, pair<pair<int, int>, int> a): tl(l), tr(r), f(a), tm(l+r>>1){}
| ^~~
nafta.cpp: In constructor 'Sgt::Sgt(long long int, long long int)':
nafta.cpp:71:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
71 | int tm = tl+tr>>1;
| ~~^~~
nafta.cpp: In function 'std::pair<long long int, long long int> solve(long long int)':
nafta.cpp:118:6: warning: statement has no effect [-Wunused-value]
118 | dbg(dp, m);
| ^~
nafta.cpp:13:19: note: in definition of macro 'dbg'
13 | #define dbg(x, y) x
| ^
nafta.cpp: In function 'int main()':
nafta.cpp:148:6: warning: statement has no effect [-Wunused-value]
148 | dbg(active, m+1);
| ^~~~~~
nafta.cpp:13:19: note: in definition of macro 'dbg'
13 | #define dbg(x, y) x
| ^
nafta.cpp:153:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
153 | while (ptr < ranges.size() && ranges[ptr].f.f == i){
| ~~~~^~~~~~~~~~~~~~~
nafta.cpp:163:8: warning: statement has no effect [-Wunused-value]
163 | debug(ranges);
| ^~~~~~
nafta.cpp:12:18: note: in definition of macro 'debug'
12 | #define debug(x) x
| ^
nafta.cpp:164:6: warning: statement has no effect [-Wunused-value]
164 | dbg(active, m);
| ^~~~~~
nafta.cpp:13:19: note: in definition of macro 'dbg'
13 | #define dbg(x, y) x
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
3676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
3676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
3676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
