Submission #901672

#TimeUsernameProblemLanguageResultExecution timeMemory
901672NourWaelNafta (COI15_nafta)C++17
34 / 100
1102 ms74320 KiB
#include <bits/stdc++.h> using namespace std; int const mxN = 2e3+2; int n,m,k, a[mxN][mxN], dp[mxN][mxN], c = 0; int inC[mxN][mxN], first_col[mxN*mxN], cost[mxN*mxN]; bool vis[mxN][mxN]; vector<int> pref [mxN]; vector<int> col [mxN]; bool valid ( int i, int j ) { if(i<0 || j<0 || i==n || j==m) return false; if(a[i][j]==-1 || vis[i][j]) return false; vis[i][j] = 1; return true; } int dfs ( int i, int j) { int ans = a[i][j]; inC[i][j] = c; first_col[c] = min ( j, first_col[c] ); if( valid(i+1,j) ) ans+=dfs(i+1,j); if( valid(i,j+1) ) ans+=dfs(i,j+1); if( valid(i-1,j) ) ans+=dfs(i-1,j); if( valid(i,j-1) ) ans+=dfs(i,j-1); return ans; } void solve ( int l, int r, int indl , int indr, int sz ) { if(l>r) return; int mid = (l+r)/2, ind = mid, maxi = 0; for(int i=indl; i<=min(indr, mid-1); i++) { int ans = dp[i][sz-1]; int d = upper_bound(col[mid].begin(),col[mid].end(),i) - col[mid].begin(); if(d!=col[mid].size()) { ans += pref[mid].back(); if(d) ans -= pref[mid][d-1]; } if(ans>maxi) { maxi = ans; ind = i; } } dp[mid][sz] = maxi; solve(l,mid-1, indl, ind, sz), solve(mid+1, r, ind, indr, sz); } signed main (){ ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin>>n>>m; for(int i=0; i<n; i++) for(int j=0; j<m; j++) { char x; cin>>x; if(x=='.') a[i][j] = -1; else a[i][j] = x-'0'; } for(int i=0; i<n; i++) for(int j=0; j<m; j++) if(!vis[i][j] && a[i][j]>-1) { vis[i][j] = 1; c++; first_col[c] = 1e9; cost[c] = dfs(i,j); } for(int j=0; j<m; j++) { set<int> st; int ans = 0; for(int i=0; i<n; i++) { if(st.find(inC[i][j])==st.end() && a[i][j]>-1 ) { ans+=cost[inC[i][j]]; st.insert(inC[i][j]); } } dp[j][1] = ans; } for(int j=0; j<m; j++) { set<int>st; for(int i=0; i<n; i++) if(a[i][j]>-1) st.insert(inC[i][j]); vector<pair<int,int>> v; for(auto it:st ) v.push_back({first_col[it], it}); sort(v.begin(),v.end()); for(int h=0; h<v.size(); h++) { col[j].push_back(v[h].first), pref[j].push_back(cost[v[h].second]); if(h) pref[j][h] += pref[j][h-1]; } } for(int i=2; i<=m; i++) solve(0,m-1, 0, m-1, i); for(int i=1; i<=m; i++) { int maxi = 0; for(int h=0; h<m; h++) maxi = max ( maxi, dp[h][i]); cout<<maxi<<'\n'; } return 0; }

Compilation message (stderr)

nafta.cpp: In function 'void solve(int, int, int, int, int)':
nafta.cpp:35:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |    if(d!=col[mid].size()) { ans += pref[mid].back(); if(d) ans -= pref[mid][d-1]; }
      |       ~^~~~~~~~~~~~~~~~~
nafta.cpp: In function 'int main()':
nafta.cpp:83:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |       for(int h=0; h<v.size(); h++) {
      |                    ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...