oj.uz

Submission #901671

# Submission time Handle Problem Language Result Execution time Memory
901671 2024-01-09T22:27:03 Z NourWael Nafta (COI15_nafta) C++17
34 / 100
 1000 ms 130400 KB 
#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;
}

Compilation message

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 2 ms 10856 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 2 ms 10856 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 16 ms 24152 KB Output is correct
8 Correct 20 ms 24152 KB Output is correct
9 Correct 12 ms 25436 KB Output is correct
10 Correct 15 ms 24668 KB Output is correct
11 Correct 18 ms 24652 KB Output is correct
12 Correct 16 ms 24436 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 2 ms 10856 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 16 ms 24152 KB Output is correct
8 Correct 20 ms 24152 KB Output is correct
9 Correct 12 ms 25436 KB Output is correct
10 Correct 15 ms 24668 KB Output is correct
11 Correct 18 ms 24652 KB Output is correct
12 Correct 16 ms 24436 KB Output is correct
13 Execution timed out 1022 ms 130400 KB Time limit exceeded
14 Halted 0 ms 0 KB -