oj.uz

Submission #901676

# Submission time Handle Problem Language Result Execution time Memory
901676 2024-01-09T22:39:06 Z NourWael Nafta (COI15_nafta) C++14
0 / 100
 10 ms 18012 KB 
#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++) {
        if(col[j].size() && col[j].back()==v[h].first) pref[j].back()+=cost[v[h].second];
        else { 
          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

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++) {
      |                    ~^~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 18012 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 18012 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 18012 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -