| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 931181 |
2024-02-21T10:53:14 Z |
dosts |
Nafta (COI15_nafta) |
C++17 |
|
0 ms |
0 KB |
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define sp << " " <<
//#define int long long
#define ff first
#define ss second
#define vi vector<int>
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
template<typename T1, typename T2> bool MIN(T1 &a, T2 b){return a > b ? a = b, true : false;}
template<typename T1, typename T2> bool MAX(T1 &a, T2 b){return a < b ? a = b, true : false;}
const int N = 2e3+2,inf = 2e18;
pii dad[N][N];
int sm[N][N];
pii find(int x,int y) {
if (pii{x,y} == dad[x][y]) return dad[x][y];
return dad[x][y] = find(dad[x][y].first,dad[x][y].second);
}
void unite(int x1,int y1,int x2,int y2) {
sm[find(x2,y2).first][find(x2,y2).second]+=sm[find(x1,y1).first][find(x1,y1).second];
dad[find(x1,y1).first][find(x1,y1).second] = find(x2,y2);
}
int common[N][N];
int util[N];
int sag[N][N];
vector<pii> edges[N][N];
int vis[N][N];
void dfs(int x,int y,int z) {
if (vis[x][y]) return;
vis[x][y] = 1;
sag[x][y] = z;
for (auto it : edges[x][y]) dfs(it.first,it.second,z);
}
vi dp_prev(N,0),dp(N,0);
void dnc(int optl,int optr,int l,int r) {
if (l > r) return;
int m = (l+r) >> 1;
int opt = optl,best = 0;
for (int i=optl;i<=min(optr,m-1);i++) {
if (dp_prev[i]+util[m]-common[i][m] > best) {
best = dp_prev[i]+util[m]-common[i][m];
opt = i;
};
}
dp[m] = best;
dnc(optl,opt,l,m-1);
dnc(opt,optr,m+1,r);
}
void solve() {
int n,m;
cin >> n >> m;
for (int i=1;i<=m;i++) for (int j=1;j<=m;j++) common[i][j] = 0;
for (int i=1;i<=m;i++) util[i] = 0;
vector<vi> a(n+1,vi(m+1));
int dot = '.'-'0';
for (int i=1;i<=n;i++) {
string s;
cin >> s;
for (int j=1;j<=m;j++) {
if (s[j-1]>='0' && s[j-1] <= '9') {
a[i][j] = s[j-1]-'0';
}
else a[i][j] = -2;
}
}
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) dad[i][j] = {i,j},sm[i][j] = max(0ll,a[i][j]);
vi dx{1,0,-1,0},dy{0,1,0,-1};
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
if(a[i][j] == dot) continue;
for (int d = 0;d<4;d++) {
int gx = i+dx[d],gy = j+dy[d];
if (gx < 1 || gx > n || gy < 1 || gy > m) continue;
if (a[gx][gy] == dot) continue;
edges[i][j].push_back({gx,gy});
edges[gx][gy].push_back({i,j});
if (find(i,j) == find(gx,gy)) continue;
unite(i,j,gx,gy);
}
}
}
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) vis[i][j] = 0;
for (int i=m;i>=1;i--){
for (int j = 1;j<=n;j++) {
dfs(j,i,i);
}
}
int got[n+1][m+1];
memset(got,0,sizeof got);
for (int i=1;i<=m;i++) {
vector<pair<pii,int>> pushed;
for (int r=1;r<=n;r++) {
if (a[r][i] == dot) continue;
auto[x,y] = find(r,i);
pushed.push_back({{x,y},r});
}
for (auto itt : pushed) {
pii it = itt.first;
int r = itt.second;
if (got[it.first][it.second]) continue;
got[it.first][it.second] = 1;
util[i]+=sm[it.first][it.second];
common[i][i]+=sm[it.first][it.second];
common[i][sag[r][i]+1]-=sm[it.first][it.second];
}
for (auto it : pushed) if (got[it.ff.first][it.ff.second]) got[it.ff.first][it.ff.second] = 0;
}
for (int i=1;i<=m;i++) {
for (int j=i+1;j<=m;j++) common[i][j]+=common[i][j-1];
}
for (int i=1;i<=m;i++) {
for (int j=1;j<i;j++) common[i][j]= common[j][i];
}
for (int i=1;i<=m;i++) dp_prev[i] = util[i];
cout << *max_element(dp_prev.begin()+1,dp_prev.end()) << '\n';
for (int i=2;i<=m;i++) {
dnc(0,m,1,m);
cout << *max_element(dp.begin(),dp.end());
if(i != m) cout << '\n';
dp_prev = dp;
for (int j=1;j<=m;j++) dp[j] = 0;
}
}
signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Dodi
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t = 1;
//cin >> t;
while (t --> 0) solve();
}
Compilation message
nafta.cpp:14:28: warning: overflow in conversion from 'double' to 'int' changes value from '2.0e+18' to '2147483647' [-Woverflow]
14 | const int N = 2e3+2,inf = 2e18;
| ^~~~
nafta.cpp: In function 'void solve()':
nafta.cpp:76:95: error: no matching function for call to 'max(long long int, __gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type&)'
76 | for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) dad[i][j] = {i,j},sm[i][j] = max(0ll,a[i][j]);
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from nafta.cpp:2:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
254 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: template argument deduction/substitution failed:
nafta.cpp:76:95: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'})
76 | for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) dad[i][j] = {i,j},sm[i][j] = max(0ll,a[i][j]);
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from nafta.cpp:2:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
300 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: template argument deduction/substitution failed:
nafta.cpp:76:95: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'})
76 | for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) dad[i][j] = {i,j},sm[i][j] = max(0ll,a[i][j]);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from nafta.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
3480 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: template argument deduction/substitution failed:
nafta.cpp:76:95: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
76 | for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) dad[i][j] = {i,j},sm[i][j] = max(0ll,a[i][j]);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from nafta.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
3486 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: template argument deduction/substitution failed:
nafta.cpp:76:95: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
76 | for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) dad[i][j] = {i,j},sm[i][j] = max(0ll,a[i][j]);
| ^
