Submission #901654

#	Time	Username	Problem	Language	Result	Execution time	Memory
901654		NourWael	Nafta (COI15_nafta)	C++17	11 / 100	1075 ms	23776 KiB

nafta

#include <bits/stdc++.h>
using namespace std;
#define int long long 
int const mxN = 2e3+5;
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];

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];
   set<int>st;
   for(int h=0; h<n; h++){
      if(a[h][mid]!=-1 && st.find(inC[h][mid])==st.end() && first_col[inC[h][mid]]>i ) { ans+= cost[inC[h][mid]];st.insert(inC[h][mid]); }
   }
   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 (){
     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;
      //cout<<j<<' '<<dp[j][1]<<'\n';
     }
    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;
} 

• Subtask 1: 11 / 11
• Subtask 2: 0 / 23
• Subtask 3: 0 / 66