oj.uz

Submission #1059831

# Submission time Handle Problem Language Result Execution time Memory
1059831 2024-08-15T08:33:40 Z dozer Soccer Stadium (IOI23_soccer) C++17
30 / 100
 4500 ms 566544 KB 
#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<pair<vector<pii>, int>, int> m;


int check(vector<pii> &r){
    if (r.size() <= 1) 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, ind})) return m[{curr, ind}];
    int n = pre.size();
    if (ind == n){
        return m[{curr, ind}] = 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});
            int res = f(curr, pre, ind + 1);
            ans = max(ans, res + j - i + 1);
            curr.pop_back();
        }
    }


    if (curr.empty()) ans = max(ans, f(curr, pre, ind + 1));
    return m[{curr, ind}] = 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

soccer.cpp: In function 'int check(std::vector<std::pair<int, int> >&)':
soccer.cpp:35: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]
   35 |     for (int i = 1; i < r.size(); i++){
      |                     ~~^~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 860 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Execution timed out 4592 ms 566544 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 860 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 344 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 344 KB ok
9 Correct 1 ms 348 KB ok
10 Correct 1 ms 348 KB ok
11 Correct 1 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 868 ms 107332 KB ok
16 Correct 133 ms 16568 KB ok
17 Correct 3 ms 860 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 416 KB ok
21 Correct 0 ms 344 KB ok
22 Correct 1 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 3 ms 856 KB ok
26 Correct 28 ms 3456 KB ok

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 860 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Execution timed out 4592 ms 566544 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 860 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Execution timed out 4592 ms 566544 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 860 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Execution timed out 4592 ms 566544 KB Time limit exceeded
5 Halted 0 ms 0 KB -