oj.uz

Submission #1065710

# Submission time Handle Problem Language Result Execution time Memory
1065710 2024-08-19T11:09:37 Z GrindMachine Soccer Stadium (IOI23_soccer) C++17
64 / 100
 1252 ms 2097152 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
https://blog.brucemerry.org.za/2023/11/ioi-2023-day-1.html

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "soccer.h"

int biggest_stadium(int n, std::vector<std::vector<int>> A)
{
    int a[n+5][n+5];
    memset(a,0,sizeof a);
    rep1(i,n) rep1(j,n) a[i][j] = A[i-1][j-1];

    int mx_extend[n+5][n+5];
    memset(mx_extend,0,sizeof mx_extend);
    rep1(i,n) mx_extend[i][n+1] = n;

    rev(j,n,1){
        rep1(i,n){
            if(!a[i][j]){
                mx_extend[i][j] = mx_extend[i][j+1];
            }
            else{
                mx_extend[i][j] = j-1;
            }
        }
    }

    int p[n+5][n+5];
    memset(p,0,sizeof p);
    rep1(i,n){
        rep1(j,n){
            p[i][j] = p[i-1][j]+a[i][j];
        }
    }

    int dp[n+5][n+5][n+5];
    memset(dp,0,sizeof dp);

    int ans = 0;

    rep1(l,n){
        rev(i,n,1){
            int r = inf1;
            for(int j = i; j <= n; ++j){
                amin(r,mx_extend[j][l]);
                if(p[j][l]-p[i-1][l]) conts;
                int len = r-l+1;
                dp[i][j][l] = max(dp[i+1][j][l],dp[i][j-1][l])+len;
                amax(dp[i][j][l],dp[i][j][l-1]);
                amax(ans,dp[i][j][l]);
            }
        }
    }

    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 0 ms 432 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 344 KB ok
5 Correct 0 ms 436 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 7 ms 4956 KB ok
8 Correct 730 ms 510032 KB ok
9 Runtime error 1252 ms 2097152 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 0 ms 432 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 1 ms 348 KB ok
10 Correct 0 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 0 ms 344 KB ok
2 Correct 1 ms 348 KB ok
3 Correct 0 ms 432 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 0 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
14 Correct 0 ms 348 KB ok
15 Correct 1 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 1 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 1 ms 348 KB ok
22 Correct 1 ms 348 KB ok
23 Correct 1 ms 348 KB ok
24 Correct 1 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 1 ms 348 KB ok
3 Correct 0 ms 432 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 348 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 1 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 1 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 1 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 1 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 1 ms 348 KB ok
24 Correct 1 ms 348 KB ok
25 Correct 1 ms 348 KB ok
26 Correct 1 ms 348 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 0 ms 348 KB ok
29 Correct 1 ms 348 KB ok
30 Correct 0 ms 604 KB ok
31 Correct 1 ms 604 KB ok
32 Correct 1 ms 600 KB ok
33 Correct 0 ms 604 KB ok
34 Correct 1 ms 604 KB ok
35 Correct 0 ms 604 KB ok
36 Correct 1 ms 604 KB ok
37 Correct 1 ms 604 KB ok
38 Correct 1 ms 432 KB ok
39 Correct 0 ms 604 KB ok
40 Correct 0 ms 604 KB ok
41 Correct 1 ms 604 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 1 ms 348 KB ok
3 Correct 0 ms 432 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 348 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 1 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 1 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 1 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 1 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 1 ms 348 KB ok
24 Correct 1 ms 348 KB ok
25 Correct 1 ms 348 KB ok
26 Correct 1 ms 348 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 0 ms 348 KB ok
29 Correct 1 ms 348 KB ok
30 Correct 0 ms 604 KB ok
31 Correct 1 ms 604 KB ok
32 Correct 1 ms 600 KB ok
33 Correct 0 ms 604 KB ok
34 Correct 1 ms 604 KB ok
35 Correct 0 ms 604 KB ok
36 Correct 1 ms 604 KB ok
37 Correct 1 ms 604 KB ok
38 Correct 1 ms 432 KB ok
39 Correct 0 ms 604 KB ok
40 Correct 0 ms 604 KB ok
41 Correct 1 ms 604 KB ok
42 Correct 365 ms 509780 KB ok
43 Correct 357 ms 509848 KB ok
44 Correct 505 ms 509780 KB ok
45 Correct 580 ms 509820 KB ok
46 Correct 402 ms 509776 KB ok
47 Correct 781 ms 510036 KB ok
48 Correct 481 ms 509828 KB ok
49 Correct 508 ms 510192 KB ok
50 Correct 603 ms 509940 KB ok
51 Correct 422 ms 509952 KB ok
52 Correct 387 ms 510036 KB ok
53 Correct 355 ms 509704 KB ok
54 Correct 359 ms 509944 KB ok
55 Correct 386 ms 509780 KB ok
56 Correct 417 ms 510040 KB ok
57 Correct 603 ms 509728 KB ok
58 Correct 557 ms 509920 KB ok
59 Correct 561 ms 509780 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 1 ms 348 KB ok
3 Correct 0 ms 432 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 0 ms 436 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 7 ms 4956 KB ok
9 Correct 730 ms 510032 KB ok
10 Runtime error 1252 ms 2097152 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -