fork download
copy 
  1. #include <algorithm>
  2. #include <array>
  3. #include <bitset>
  4. #include <cassert>
  5. #include <chrono>
  6. #include <cmath>
  7. #include <cstring>
  8. #include <functional>
  9. #include <iomanip>
  10. #include <iostream>
  11. #include <limits>
  12. #include <map>
  13. #include <numeric>
  14. #include <queue>
  15. #include <random>
  16. #include <set>
  17. #include <vector>
  18. using namespace std;
  19.  
  20. template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
  21. template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; } 
  22. void dbg_out() { cout << endl; }
  23. template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
  24.  
  25. #ifdef imtiyazrasool92
  26. #define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
  27. #else
  28. #define dbg(...)
  29. #endif
  30.  
  31. const int nax = 200;
  32.  
  33. void run_case(){
  34.     int N,K;
  35.     cin >> N >> K;
  36.     vector<vector<int>> A(nax,vector<int> (nax));
  37.     int curr = 0;
  38.     for(int i = 0,x1,x2,y1,y2;i < N;i++){
  39.         cin >> x1 >> y1 >> x2 >> y2;
  40.         A[x1][y1]++;
  41.         if(y2 < nax)
  42.             A[x1][y2]--;
  43.         if(x2 < nax)
  44.             A[x2][y1]--;
  45.         if(x2 < nax && y2 < nax)
  46.             A[x2][y2]++;
  47.     }
  48.     vector<vector<int>> actual(nax,vector<int> (nax));
  49.     for(int i = 0;i < nax;i++){
  50.         for(int j = 0;j < nax;j++){
  51.             if(j > 0){
  52.                 A[i][j] += A[i][j - 1];
  53.             }
  54.             if(i > 0){
  55.                 A[i][j] += A[i - 1][j];
  56.             }
  57.             if(i > 0 && j > 0){
  58.                 A[i][j] -= A[i - 1][j - 1];
  59.             }
  60.             if(A[i][j] == K){
  61.                 actual[i][j] = -1;
  62.                 curr++;
  63.             }
  64.             if(A[i][j] == K - 1)
  65.                 actual[i][j] = 1;
  66.         }
  67.     }
  68.     vector<vector<int>> leftup,rightup,leftdown,rightdown;
  69.     leftup = rightup = leftdown = rightdown = actual;
  70.     for(int i = 0;i < nax;i++){
  71.         for(int j = 1;j < nax;j++){
  72.             leftup[i][j] += leftup[i][j - 1];
  73.             leftdown[i][j] += leftdown[i][j - 1];
  74.         }
  75.     }
  76.     for(int i = nax - 1;i>=0;i--){
  77.         for(int j = nax - 2;j>=0;j--){
  78.             rightup[i][j] += rightup[i][j + 1];
  79.             rightdown[i][j] += rightdown[i][j + 1];
  80.         }   
  81.     }
  82.     for(int i = 1;i < nax;i++){
  83.         for(int j = 0;j < nax;j++){
  84.             leftup[i][j] += leftup[i - 1][j];
  85.             rightup[i][j] += rightup[i - 1][j];
  86.         }
  87.     }
  88.     for(int i = nax - 2;i>=0;i--){
  89.         for(int j = 0;j < nax;j++){
  90.             leftdown[i][j] += leftdown[i + 1][j];
  91.             rightdown[i][j] += rightdown[i + 1][j];
  92.         }   
  93.     }
  94.     // max
  95.     for(int i = 0;i < nax;i++){
  96.         for(int j = 1;j < nax;j++){
  97.             leftup[i][j] = max(leftup[i][j - 1],leftup[i][j]);
  98.             leftdown[i][j] = max(leftdown[i][j],leftdown[i][j - 1]);
  99.         }
  100.     }
  101.     for(int i = nax - 1;i>=0;i--){
  102.         for(int j = nax - 2;j>=0;j--){
  103.             rightup[i][j] = max(rightup[i][j + 1],rightup[i][j]);
  104.             rightdown[i][j] = max(rightdown[i][j + 1],rightdown[i][j]);
  105.         }   
  106.     }
  107.     for(int i = 1;i < nax;i++){
  108.         for(int j = 0;j < nax;j++){
  109.             leftup[i][j] = max(leftup[i][j],leftup[i - 1][j]);
  110.             rightup[i][j] = max(rightup[i][j],rightup[i - 1][j]);
  111.         }
  112.     }
  113.     for(int i = nax - 2;i>=0;i--){
  114.         for(int j = 0;j < nax;j++){
  115.             leftdown[i][j] = max(leftdown[i][j],leftdown[i + 1][j]);
  116.             rightdown[i][j] = max(rightdown[i][j],rightdown[i + 1][j]);
  117.         }   
  118.     }
  119.     auto max_of = [](vector<int> Y){
  120.         sort(Y.rbegin(),Y.rend());
  121.         return Y[0] + Y[1];
  122.     };
  123.     int answer = 0;
  124.     for(int i = 0;i < nax + 1;i++){
  125.         for(int j = 0;j < nax + 1;j++){
  126.             int a = 0,b = 0,c = 0,d = 0;
  127.             if(i && j){
  128.                 a = max(a,leftup[i - 1][j - 1]);
  129.             }
  130.             if(i && j < nax){
  131.                 b = max(b,rightup[i - 1][j]);
  132.             }
  133.             if(i < nax && j < nax){
  134.                 c = max(c,rightdown[i][j]);
  135.             }
  136.             if(i < nax && j){
  137.                 d = max(d,leftdown[i][j - 1]);
  138.             }
  139.             answer = max(answer,max_of({a,b,c,d}));
  140.         }
  141.     }
  142.     cout << answer + curr;
  143. }
  144.  
  145. int main(){
  146.     cin.tie(0)->sync_with_stdio(0);
  147.     // freopen("paintbarn.in","r",stdin);
  148.     // freopen("paintbarn.out","w",stdout);
  149.     int tests = 1;
  150.     // cin >> tests;
  151.     while(tests--){
  152.         run_case();
  153.         cout << '\n';
  154.     }
  155. }
Success #stdin #stdout 0.01s 5540KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
40000
https://ideone.com/XllgSW
language:
C++14 (gcc 8.3)
created:
2 years 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!