top of page

CCC '22 J5 - Square Pool

#include<iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

bool rowcom(pair<int, int> a, pair<int, int> b){
   return a.first < b.first;
}

bool colcom(pair<int, int> a, pair<int, int> b){
   return a.second < b.second;
}

int main()
{
   int n , t;
   cin >> n;
   cin >> t;
   vector<pair<int, int>> a(t+2);
   vector<pair<int, int>> b(t+2);
   a[0] = {0, 0};
   b[0] = {0, 0};
   for(int i = 1; i <= t; i++){
      cin >> a[i].first;
      cin >> a[i].second;
      b[i].first = a[i].first;
      b[i].second = a[i].second;
   }
   a[t+1] ={n+1, n+1};
   b[t+1] ={n+1, n+1};
   sort(a.begin(), a.end(), rowcom);
   sort(b.begin(), b.end(), colcom);
   int result = 0;
   for(int k = 0; k <= t; k++){
      pair<int, int> l = a[k];
      for(int i = k+1; i <= t+1; i++){
         pair<int, int> r = a[i];
         int ma = 0;
         int pre = 0;
         int d = r.first - l.first - 1;
        
         for(int j = 1; j <= t; j++){
            pair<int, int> tt = b[j];
            if(tt.first < r.first && tt.first > l.first){
               ma = max(ma, tt.second- pre - 1);
               pre = tt.second;
            }
         }
         ma = max(ma, n + 1 - pre - 1);
         result = max(result, min(d, ma));
      }
   }
   cout<<result<<endl;
}

Recent Posts

See All

CCC '24 J5 - Harvest Waterloo

#include<iostream> #include <vector> #include <algorithm> #include <cmath> #include <stack> using namespace std; int main() { int r, c, sr, sc; cin >> r; cin >> c; int p[r][c]; bool v

CCC '24 J4 - Troublesome Keys

#include <iostream> #include <string> #include <map> #include <vector> #include <algorithm> #include <cmath> using namespace std; int main() { string ps; string ds; cin >> ps; cin >> ds;

CCC 2013 J5/S3

#include <iostream> #include <string> #include <map> #include <vector> #include <algorithm> #include <cmath> using namespace std; char itlist[3] = {'W','L','T'}; int num_of_games_left = 0; int resul

Comments


bottom of page