제출 #901671

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
901671		NourWael	Nafta (COI15_nafta)	C++17	34 / 100	1022 ms	130400 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];
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;
} 

컴파일 시 표준 에러 (stderr) 메시지

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

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