oj.uz

Submission #915915

# Submission time Handle Problem Language Result Execution time Memory
915915 2024-01-24T21:52:39 Z biank Soccer Stadium (IOI23_soccer) C++17
48 / 100
 4500 ms 1962820 KB 
#include <bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define SIZE(x) (int)x.size()
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define forn(i,n) for(int i=0;i<int(n);i++)
#define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--)
#define dforn(i,n) for(int i=int(n)-1;i>=0;i--)
#define fst first
#define snd second
typedef long long ll;
typedef pair<int,int> ii;
const int MAXN = 500;
int f[MAXN][MAXN];
pair<ll,ii> dp[MAXN][MAXN][MAXN];
int L[MAXN][MAXN], R[MAXN][MAXN];

int n;

pair<ll,ii> solve(int l, int r, int p) {
    if(l>r) return {0LL,{-1,n}};
    if(dp[l][r][p].fst!=-1) return dp[l][r][p];
    auto calculate = [&](pair<int,ii> prev, int i) {
        auto [val,range] = prev;
        int mini = max(range.fst, L[i][p]), maxi = min(range.snd, R[i][p]);
        return (pair<ll,ii>){val+max(maxi-mini-1,0),{mini,maxi}};
    };
    return dp[l][r][p] = max(calculate(solve(l+1,r,p),l),
                            calculate(solve(l,r-1,p),r));
}

int biggest_stadium(int N, vector<vector<int>> F) {
    n=N;
    forn(i,n) forn(j,n) {
        f[i][j]=F[i][j];
    }
    forn(i,n) forn(j,n) forn(k,n) {
        dp[i][j][k].fst = -1;
    }
    forn(i,n) {
        int k=-1;
        forn(j,n) {
            if(f[i][j]==1) k=j;
            L[i][j]=k;
        }
    }
    forn(i,n) {
        int k=n;
        dforn(j,n) {
            if(f[i][j]==1) k=j;
            R[i][j]=k;
        }
    }
    ll ans = 0LL;
    forn(i,n) {
        ll curr = solve(0,n-1,i).fst;
        ans=max(ans,curr);
    }
    return int(ans);
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB ok
2 Correct 2 ms 8536 KB ok
3 Correct 4 ms 20828 KB ok
4 Correct 5 ms 23000 KB ok
5 Correct 1 ms 4444 KB ok
6 Correct 1 ms 8540 KB ok
7 Correct 56 ms 289880 KB ok
8 Execution timed out 4612 ms 1962588 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB ok
2 Correct 2 ms 8536 KB ok
3 Correct 2 ms 8536 KB ok
4 Correct 2 ms 8536 KB ok
5 Correct 2 ms 8540 KB ok
6 Correct 2 ms 8536 KB ok
7 Correct 2 ms 8540 KB ok
8 Correct 1 ms 8540 KB ok
9 Correct 1 ms 8540 KB ok
10 Correct 1 ms 8540 KB ok
11 Correct 2 ms 8540 KB ok
12 Correct 1 ms 8644 KB ok
13 Correct 2 ms 8540 KB ok
14 Correct 2 ms 8540 KB ok
15 Correct 3 ms 16732 KB ok
16 Correct 3 ms 16732 KB ok
17 Correct 3 ms 16732 KB ok
18 Correct 3 ms 16732 KB ok
19 Correct 4 ms 16732 KB ok
20 Correct 3 ms 16728 KB ok
21 Correct 3 ms 16732 KB ok
22 Correct 3 ms 16732 KB ok
23 Correct 4 ms 16732 KB ok
24 Correct 3 ms 16732 KB ok
25 Correct 3 ms 16732 KB ok
26 Correct 3 ms 16728 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB ok
2 Correct 2 ms 8536 KB ok
3 Correct 2 ms 8536 KB ok
4 Correct 4 ms 20828 KB ok
5 Correct 5 ms 23000 KB ok
6 Correct 2 ms 8536 KB ok
7 Correct 2 ms 8540 KB ok
8 Correct 2 ms 8536 KB ok
9 Correct 2 ms 8540 KB ok
10 Correct 1 ms 8540 KB ok
11 Correct 1 ms 8540 KB ok
12 Correct 1 ms 8540 KB ok
13 Correct 2 ms 8540 KB ok
14 Correct 1 ms 8644 KB ok
15 Correct 2 ms 8540 KB ok
16 Correct 2 ms 8540 KB ok
17 Correct 3 ms 16732 KB ok
18 Correct 3 ms 16732 KB ok
19 Correct 3 ms 16732 KB ok
20 Correct 3 ms 16732 KB ok
21 Correct 4 ms 16732 KB ok
22 Correct 3 ms 16728 KB ok
23 Correct 3 ms 16732 KB ok
24 Correct 3 ms 16732 KB ok
25 Correct 4 ms 16732 KB ok
26 Correct 3 ms 16732 KB ok
27 Correct 3 ms 16732 KB ok
28 Correct 3 ms 16728 KB ok
29 Correct 3 ms 16732 KB ok
30 Correct 10 ms 68188 KB ok
31 Correct 9 ms 68140 KB ok
32 Correct 11 ms 68188 KB ok
33 Correct 10 ms 68184 KB ok
34 Correct 10 ms 68400 KB ok
35 Correct 10 ms 68184 KB ok
36 Correct 10 ms 68184 KB ok
37 Correct 10 ms 68188 KB ok
38 Correct 11 ms 68188 KB ok
39 Correct 11 ms 68184 KB ok
40 Correct 10 ms 68188 KB ok
41 Correct 11 ms 68188 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB ok
2 Correct 2 ms 8536 KB ok
3 Correct 2 ms 8536 KB ok
4 Correct 4 ms 20828 KB ok
5 Correct 5 ms 23000 KB ok
6 Correct 2 ms 8536 KB ok
7 Correct 2 ms 8540 KB ok
8 Correct 2 ms 8536 KB ok
9 Correct 2 ms 8540 KB ok
10 Correct 1 ms 8540 KB ok
11 Correct 1 ms 8540 KB ok
12 Correct 1 ms 8540 KB ok
13 Correct 2 ms 8540 KB ok
14 Correct 1 ms 8644 KB ok
15 Correct 2 ms 8540 KB ok
16 Correct 2 ms 8540 KB ok
17 Correct 3 ms 16732 KB ok
18 Correct 3 ms 16732 KB ok
19 Correct 3 ms 16732 KB ok
20 Correct 3 ms 16732 KB ok
21 Correct 4 ms 16732 KB ok
22 Correct 3 ms 16728 KB ok
23 Correct 3 ms 16732 KB ok
24 Correct 3 ms 16732 KB ok
25 Correct 4 ms 16732 KB ok
26 Correct 3 ms 16732 KB ok
27 Correct 3 ms 16732 KB ok
28 Correct 3 ms 16728 KB ok
29 Correct 3 ms 16732 KB ok
30 Correct 10 ms 68188 KB ok
31 Correct 9 ms 68140 KB ok
32 Correct 11 ms 68188 KB ok
33 Correct 10 ms 68184 KB ok
34 Correct 10 ms 68400 KB ok
35 Correct 10 ms 68184 KB ok
36 Correct 10 ms 68184 KB ok
37 Correct 10 ms 68188 KB ok
38 Correct 11 ms 68188 KB ok
39 Correct 11 ms 68184 KB ok
40 Correct 10 ms 68188 KB ok
41 Correct 11 ms 68188 KB ok
42 Correct 4356 ms 1962820 KB ok
43 Execution timed out 4567 ms 1962596 KB Time limit exceeded
44 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB ok
2 Correct 2 ms 8536 KB ok
3 Correct 2 ms 8536 KB ok
4 Correct 4 ms 20828 KB ok
5 Correct 5 ms 23000 KB ok
6 Correct 1 ms 4444 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 56 ms 289880 KB ok
9 Execution timed out 4612 ms 1962588 KB Time limit exceeded
10 Halted 0 ms 0 KB -