Submission #1059796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059796		dozer	Soccer Stadium (IOI23_soccer)	C++17	13.50 / 100	4595 ms	583764 KiB

soccer

#include "soccer.h"
//brute fooorceee
#include <bits/stdc++.h>
using namespace std;
#define sp " " 
#define endl "\n"
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define LL node * 2
#define RR node * 2 + 1
#define ll long long
#define MAXN 35

const int modulo = 1e9 + 7;
const ll INF = 2e18 + 7;

map<vector<pii>, int> m;


int check(vector<pii> &r){
    if (r.empty()) return 1;

    for (auto i : r){
        for (auto j : r){
            int l = j.st, r = j.nd;
            if (l < i.st && r < i.nd) return 0;
            if (l > i.st && r > i.nd) return 0;
        }
    }
    int dec = 0;
    pii last = r.front();
    for (int i = 1; i < r.size(); i++){
        if (r[i].st > last.st || r[i].nd < last.nd){
            dec = 1;
        }
        else if (r[i].st < last.st || r[i].nd > last.nd){
            if (dec == 1) return 0;
        }
        last = r[i];
    }
    return 1;
}


int f(vector<pii> &curr, vector<vector<int>> &pre, int ind){
    if (check(curr) == 0) return -modulo;
    if (!curr.empty() && m.count(curr)) return m[curr];
    int n = pre.size();
    if (ind == n){
        return m[curr] = 0;
    }
    int ans = 0;
    for (int i = 0; i < n; i++){
        for (int j = i; j < n; j++){
            int sum = pre[ind][j];
            if (i > 0) sum -= pre[ind][i - 1];
            if (sum != 0) continue;
            curr.pb({i, j});
            ans = max(ans, f(curr, pre, ind + 1) + j - i + 1);
            curr.pop_back();
        }
    }

    if (curr.empty()) ans = max(ans, f(curr, pre, ind + 1));
    return m[curr] = ans;
}



int biggest_stadium(int N, vector<std::vector<int>> F)
{   
    int n = N;
    vector<vector<int>> pre = F;
    for (int i = 0; i < n; i++)
        for (int j = 1; j < n; j++) pre[i][j] += pre[i][j - 1];

    vector<pii> tmp;
    return f(tmp, pre, 0);
}
/*
int main()
{
    fileio();
    int N;
    assert(1 == scanf("%d", &N));
    std::vector<std::vector<int>> F(N, std::vector<int>(N));
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            assert(1 == scanf("%d", &F[i][j]));
        }
    }
    fclose(stdin);

    int res = biggest_stadium(N, F);

    printf("%d\n", res);
    fclose(stdout);
    return 0;
}*/

Compilation message (stderr)

soccer.cpp: In function 'int check(std::vector<std::pair<int, int> >&)':
soccer.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i = 1; i < r.size(); i++){
      |                     ~~^~~~~~~~~~

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