oj.uz

Submission #988643

# Submission time Handle Problem Language Result Execution time Memory
988643 2024-05-25T11:11:49 Z Gray Soccer Stadium (IOI23_soccer) C++17
0 / 100
 4500 ms 133912 KB 
#include<bits/stdc++.h>
#include "soccer.h"

using namespace std;
#define ll long long
#define ff first
#define ss second
#define ln "\n"


ll n;

int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    n=N;
    vector<vector<ll>> gr(n+1, vector<ll>(n+1));
    vector<vector<pair<ll, ll>>> A(N+2, vector<pair<ll, ll>>(N+2, {0, n+1}));
    for (ll i=1; i<=n; i++){
        for (ll j=1; j<=n; j++){
            gr[i][j]=F[i-1][j-1];
            A[i][j].ff=A[i][j-1].ff;
            if (gr[i][j]){
                A[i][j].ff=j;
            }
        }
    }
    for (ll i=1; i<=n; i++){
        for (ll j=n; j>=1; j--){
            A[i][j].ss=A[i][j+1].ss;
            if (gr[i][j]){
                A[i][j].ss=j;
            }
        }
    }
    // for (ll i=1; i<=n; i++){
    //     for (ll j=1; j<=n; j++){
    //         cout << A[i][j].ff << "|" << A[i][j].ss << " ";
    //     }
    //     cout << ln;
    // }
    // cout << ln;
    ll res=0;
    for (ll i=1; i<=n; i++){
        for (ll j=1; j<=n; j++){
            vector<ll> debug;
            ll l=A[i][j].ff, r=A[i][j].ss;
            ll ans=r-l-1;
            ll ch=i-1;
            while (ch>0 and l<j and r>j and l<r){
                l = max(l, A[ch][j].ff);
                r = min(r, A[ch][j].ss);
                ans+=r-l-1;
                ch--;
            }
            l=A[i][j].ff; r=A[i][j].ss;
            debug.push_back(ch);
            ch = i+1;
            while (ch<=n and l<j and r>j and l<r){
                l = max(l, A[ch][j].ff);
                r = min(r, A[ch][j].ss);
                ans+=r-l-1;
                ch++;
            }
            debug.push_back(ch);
            // cout << i << " " << j << " -> " << ans << ": ";
            // for (auto cch:debug){
            //     cout << cch << " "; 
            // }
            // cout << ln;
            if (res<ans){
                res=ans;
            }
        }
    }
    return res;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 1 ms 348 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 4 ms 604 KB ok
8 Correct 358 ms 8844 KB ok
9 Execution timed out 4533 ms 133912 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 1 ms 348 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Partially correct 1 ms 600 KB partial
6 Correct 1 ms 344 KB ok
7 Incorrect 0 ms 432 KB wrong
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 1 ms 344 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Partially correct 1 ms 600 KB partial
7 Correct 1 ms 344 KB ok
8 Incorrect 0 ms 432 KB wrong
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 1 ms 344 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Partially correct 1 ms 600 KB partial
9 Correct 1 ms 344 KB ok
10 Incorrect 0 ms 432 KB wrong
11 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 1 ms 344 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Partially correct 1 ms 600 KB partial
9 Correct 1 ms 344 KB ok
10 Incorrect 0 ms 432 KB wrong
11 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 1 ms 344 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 4 ms 604 KB ok
9 Correct 358 ms 8844 KB ok
10 Execution timed out 4533 ms 133912 KB Time limit exceeded
11 Halted 0 ms 0 KB -