Submission #848836

#	Time	Username	Problem	Language	Result	Execution time	Memory
848836		d4xn	Soccer Stadium (IOI23_soccer)	C++17	8 / 100	4510 ms	63368 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 2000, inf = INT_MAX;

int n, e, sum, ans; // 0 nunca usado, 1 en uso, 2 no se puede usar
vector<vector<int>> f, f2;
vector<pair<int, int>> s[2];

bool check() {
  //cerr << "a" << endl;
  bool ok = 1;
  for (int i = 0; i < n; i++) {
        int l = inf;
        int r = -inf;
        for (int j = 0; j < n; j++) {
            if (f2[i][j] != 2) continue;
            l = min(l, j);
            r = max(r, j);
        }
        s[0][i] = make_pair(l, r);

        for (int j = l; j <= r; j++) {
            if (f2[i][j] != 2) ok = 0;
        }

        l = inf;
        r = -inf;
        for (int j = 0; j < n; j++) {
            if (f2[j][i] != 2) continue;
            l = min(l, j);
            r = max(r, j);
        }
        s[1][i] = make_pair(l, r);

        for (int j = l; j <= r; j++) {
            if (f2[j][i] != 2) ok = 0;
        }
    }
//cerr << "a" << endl;
    for (int x = 0; x < n; x++) {
        for (int y = x+1; y < n; y++) {
            pair<int, int> a = s[0][x];
            pair<int, int> b = s[0][y];
            if (!(a.first <= b.first && b.second <= a.second) && !(b.first <= a.first && a.second <= b.second)) {
                ok = 0;
            }

            a = s[1][x];
            b = s[1][y];    
            if (!(a.first <= b.first && b.second <= a.second) && !(b.first <= a.first && a.second <= b.second)) {
                ok = 0;
            }
        }
    }//cerr << "a" << endl;
    return ok;
}

void gen(int idx) {
  //cerr << idx << endl;
    if (idx == n) {
      if (!check()) return;
      ans = max(ans, sum);
      return;
    }

    for (int i = 0; i < n; i++) {
      for (int j = i; j < n; j++) {
        if (f[idx][j] == 1) break;
        f2[idx][j] = 2;
        
        sum += j-i+1;
        gen(idx+1);
        sum -= j-i+1;
      }

      for (int j = i; j < n; j++) {
        if (f[idx][j] == 1) break;
        f2[idx][j] = f[idx][j];
      }
    }
}

int biggest_stadium(int N, vector<vector<int>> F) {
    n = N;
    f = f2 = F;

    // se pueden coger todas las empty cells?
    bool ok = 1;
    e = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            e += !f[i][j];
        }
    }

    s[0].resize(n);
    s[1].resize(n);
    for (int i = 0; i < n; i++) {
        int l = inf;
        int r = -inf;
        for (int j = 0; j < n; j++) {
            if (f[i][j] == 1) continue;
            l = min(l, j);
            r = max(r, j);
        }
        s[0][i] = make_pair(l, r);

        for (int j = l; j <= r; j++) {
            if (f[i][j] == 1) ok = 0;
        }

        l = inf;
        r = -inf;
        for (int j = 0; j < n; j++) {
            if (f[j][i] == 1) continue;
            l = min(l, j);
            r = max(r, j);
        }
        s[1][i] = make_pair(l, r);

        for (int j = l; j <= r; j++) {
            if (f[j][i] == 1) ok = 0;
        }
    }

    for (int x = 0; x < n; x++) {
        for (int y = x+1; y < n; y++) {
            pair<int, int> a = s[0][x];
            pair<int, int> b = s[0][y];
            if (!(a.first <= b.first && b.second <= a.second) && !(b.first <= a.first && a.second <= b.second)) {
                ok = 0;
            }

            a = s[1][x];
            b = s[1][y];    
            if (!(a.first <= b.first && b.second <= a.second) && !(b.first <= a.first && a.second <= b.second)) {
                ok = 0;
            }
        }
    }

    if (ok) return e;

    // hay solo un tree?
    if (e == n*n-1) {
        ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (f[i][j] == 1) {
                    ans = max(ans, n*n - (i+1)*(j+1));
                    ans = max(ans, n*n - (n-i)*(j+1));
                    ans = max(ans, n*n - (i+1)*(n-j));
                    ans = max(ans, n*n - (n-i)*(n-j));
                    break;
                }
            }
        }
        return ans;
    }

    // else
   sum = ans = 0;
    gen(0);
    return (ans == e ? ans-1 : ans);
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 2 / 8
• Subtask 3: 0 / 22
• Subtask 4: 0 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30