fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. const int  MAXN = 5e2+5;
  5. int v, h , n, x1, x2, c, y2, dp[MAXN][MAXN];
  6. bool a[MAXN][MAXN], vis[MAXN][MAXN];
  7. int f(int i, int j){
  8.     if ( i > v || j <1 || j > h) return 0;
  9.     if(vis[i][j]) return dp[i][j];
  10.     if(a[i][j]){
  11.         // cari pecahan air kena batu mana
  12.         int l = j, r =j;
  13.         while(a[i][l]) l--;
  14.         while (a[i][r]) r++;
  15.  
  16.         dp[i][j] = f(i, l) + f(i, r) +1;
  17.     }
  18.     else{
  19.         dp[i][j] = f(i+1, j);
  20.     }
  21.     vis[i][j] = true;
  22.     return dp[i][j];
  23. }
  24. signed main(){
  25.     cin >>v >> h >> n;
  26.     for (int i =1; i <= h; i++){
  27.         cin >> x1 >>c >> x2 >> y2;
  28.         for (int j = x1; j <= x2; j++){
  29.             for (int k = c; k <= y2; k++){
  30.                 a[j][k] = true;
  31.                 // ada batu;
  32.             }
  33.         }
  34.     }
  35.     int ans =0;
  36.     for (int i =1; i <= h; i++){
  37.         ans = max(ans, f(0, i));
  38.     }
  39.     // di titik 0,X berapa banyak titiknya
  40.     cout << ans << endl;
  41.  
  42. }
Success #stdin #stdout 0s 5528KB
comments (?)
stdin
copy 
6 6 3
2 3 2 4
4 2 5 2
5 5 6 5
stdout
copy 
3
https://ideone.com/qawaDc
language:
C++ (gcc 8.3)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!