oj.uz

Submission #848836

# Submission time Handle Problem Language Result Execution time Memory
848836 2023-09-13T15:07:18 Z d4xn Soccer Stadium (IOI23_soccer) C++17
8 / 100
 4500 ms 63368 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 344 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 344 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 1 ms 344 KB ok
8 Correct 17 ms 4244 KB ok
9 Correct 274 ms 63368 KB ok

Subtask #2
2.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 0 ms 348 KB ok
5 Partially correct 1 ms 348 KB partial
6 Correct 1 ms 344 KB ok
7 Correct 0 ms 344 KB ok
8 Correct 1 ms 344 KB ok
9 Correct 0 ms 344 KB ok
10 Correct 0 ms 344 KB ok
11 Partially correct 0 ms 344 KB partial
12 Partially correct 0 ms 344 KB partial
13 Correct 1 ms 344 KB ok

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 344 KB ok
2 Correct 1 ms 344 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 0 ms 344 KB ok
5 Correct 0 ms 348 KB ok
6 Partially correct 1 ms 348 KB partial
7 Correct 1 ms 344 KB ok
8 Correct 0 ms 344 KB ok
9 Correct 1 ms 344 KB ok
10 Correct 0 ms 344 KB ok
11 Correct 0 ms 344 KB ok
12 Partially correct 0 ms 344 KB partial
13 Partially correct 0 ms 344 KB partial
14 Correct 1 ms 344 KB ok
15 Execution timed out 4510 ms 812 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 344 KB ok
2 Correct 1 ms 344 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 0 ms 348 KB ok
8 Partially correct 1 ms 348 KB partial
9 Correct 1 ms 344 KB ok
10 Correct 0 ms 344 KB ok
11 Correct 1 ms 344 KB ok
12 Correct 0 ms 344 KB ok
13 Correct 0 ms 344 KB ok
14 Partially correct 0 ms 344 KB partial
15 Partially correct 0 ms 344 KB partial
16 Correct 1 ms 344 KB ok
17 Execution timed out 4510 ms 812 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 344 KB ok
2 Correct 1 ms 344 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 0 ms 348 KB ok
8 Partially correct 1 ms 348 KB partial
9 Correct 1 ms 344 KB ok
10 Correct 0 ms 344 KB ok
11 Correct 1 ms 344 KB ok
12 Correct 0 ms 344 KB ok
13 Correct 0 ms 344 KB ok
14 Partially correct 0 ms 344 KB partial
15 Partially correct 0 ms 344 KB partial
16 Correct 1 ms 344 KB ok
17 Execution timed out 4510 ms 812 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 344 KB ok
2 Correct 1 ms 344 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 344 KB ok
8 Correct 1 ms 344 KB ok
9 Correct 17 ms 4244 KB ok
10 Correct 274 ms 63368 KB ok
11 Correct 0 ms 344 KB ok
12 Correct 0 ms 348 KB ok
13 Partially correct 1 ms 348 KB partial
14 Correct 1 ms 344 KB ok
15 Correct 0 ms 344 KB ok
16 Correct 1 ms 344 KB ok
17 Correct 0 ms 344 KB ok
18 Correct 0 ms 344 KB ok
19 Partially correct 0 ms 344 KB partial
20 Partially correct 0 ms 344 KB partial
21 Correct 1 ms 344 KB ok
22 Execution timed out 4510 ms 812 KB Time limit exceeded
23 Halted 0 ms 0 KB -