oj.uz

Submission #915917

# Submission time Handle Problem Language Result Execution time Memory
915917 2024-01-24T21:56:45 Z biank Soccer Stadium (IOI23_soccer) C++17
48 / 100
 4500 ms 1473608 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 pair<int,int> ii;
const int MAXN = 500;
int f[MAXN][MAXN];
pair<int,ii> dp[MAXN][MAXN][MAXN];
int L[MAXN][MAXN], R[MAXN][MAXN];

int n;

pair<int,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<int,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;
        }
    }
    int ans=0;
    forn(i,n) ans=max(ans,solve(0,n-1,i).fst);
    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB ok
2 Correct 1 ms 6592 KB ok
3 Correct 3 ms 18780 KB ok
4 Correct 4 ms 20828 KB ok
5 Correct 1 ms 2396 KB ok
6 Correct 1 ms 6492 KB ok
7 Correct 49 ms 263508 KB ok
8 Execution timed out 4586 ms 1473368 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB ok
2 Correct 1 ms 6592 KB ok
3 Correct 2 ms 6852 KB ok
4 Correct 1 ms 6492 KB ok
5 Correct 1 ms 6604 KB ok
6 Correct 2 ms 6492 KB ok
7 Correct 1 ms 6488 KB ok
8 Correct 2 ms 6492 KB ok
9 Correct 2 ms 6492 KB ok
10 Correct 2 ms 6492 KB ok
11 Correct 1 ms 6492 KB ok
12 Correct 1 ms 6492 KB ok
13 Correct 1 ms 6492 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB ok
2 Correct 1 ms 6488 KB ok
3 Correct 1 ms 6592 KB ok
4 Correct 2 ms 6852 KB ok
5 Correct 1 ms 6492 KB ok
6 Correct 1 ms 6604 KB ok
7 Correct 2 ms 6492 KB ok
8 Correct 1 ms 6488 KB ok
9 Correct 2 ms 6492 KB ok
10 Correct 2 ms 6492 KB ok
11 Correct 2 ms 6492 KB ok
12 Correct 1 ms 6492 KB ok
13 Correct 1 ms 6492 KB ok
14 Correct 1 ms 6492 KB ok
15 Correct 3 ms 14692 KB ok
16 Correct 3 ms 14680 KB ok
17 Correct 2 ms 14684 KB ok
18 Correct 2 ms 14684 KB ok
19 Correct 2 ms 14684 KB ok
20 Correct 2 ms 14936 KB ok
21 Correct 2 ms 14684 KB ok
22 Correct 3 ms 14684 KB ok
23 Correct 3 ms 14684 KB ok
24 Correct 3 ms 14684 KB ok
25 Correct 3 ms 14684 KB ok
26 Correct 3 ms 14684 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB ok
2 Correct 1 ms 6488 KB ok
3 Correct 1 ms 6592 KB ok
4 Correct 3 ms 18780 KB ok
5 Correct 4 ms 20828 KB ok
6 Correct 2 ms 6852 KB ok
7 Correct 1 ms 6492 KB ok
8 Correct 1 ms 6604 KB ok
9 Correct 2 ms 6492 KB ok
10 Correct 1 ms 6488 KB ok
11 Correct 2 ms 6492 KB ok
12 Correct 2 ms 6492 KB ok
13 Correct 2 ms 6492 KB ok
14 Correct 1 ms 6492 KB ok
15 Correct 1 ms 6492 KB ok
16 Correct 1 ms 6492 KB ok
17 Correct 3 ms 14692 KB ok
18 Correct 3 ms 14680 KB ok
19 Correct 2 ms 14684 KB ok
20 Correct 2 ms 14684 KB ok
21 Correct 2 ms 14684 KB ok
22 Correct 2 ms 14936 KB ok
23 Correct 2 ms 14684 KB ok
24 Correct 3 ms 14684 KB ok
25 Correct 3 ms 14684 KB ok
26 Correct 3 ms 14684 KB ok
27 Correct 3 ms 14684 KB ok
28 Correct 3 ms 14684 KB ok
29 Correct 3 ms 14680 KB ok
30 Correct 10 ms 64088 KB ok
31 Correct 10 ms 64092 KB ok
32 Correct 10 ms 64092 KB ok
33 Correct 9 ms 64092 KB ok
34 Correct 11 ms 64088 KB ok
35 Correct 10 ms 64092 KB ok
36 Correct 9 ms 64092 KB ok
37 Correct 10 ms 64088 KB ok
38 Correct 9 ms 64092 KB ok
39 Correct 10 ms 64036 KB ok
40 Correct 9 ms 64092 KB ok
41 Correct 10 ms 64088 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB ok
2 Correct 1 ms 6488 KB ok
3 Correct 1 ms 6592 KB ok
4 Correct 3 ms 18780 KB ok
5 Correct 4 ms 20828 KB ok
6 Correct 2 ms 6852 KB ok
7 Correct 1 ms 6492 KB ok
8 Correct 1 ms 6604 KB ok
9 Correct 2 ms 6492 KB ok
10 Correct 1 ms 6488 KB ok
11 Correct 2 ms 6492 KB ok
12 Correct 2 ms 6492 KB ok
13 Correct 2 ms 6492 KB ok
14 Correct 1 ms 6492 KB ok
15 Correct 1 ms 6492 KB ok
16 Correct 1 ms 6492 KB ok
17 Correct 3 ms 14692 KB ok
18 Correct 3 ms 14680 KB ok
19 Correct 2 ms 14684 KB ok
20 Correct 2 ms 14684 KB ok
21 Correct 2 ms 14684 KB ok
22 Correct 2 ms 14936 KB ok
23 Correct 2 ms 14684 KB ok
24 Correct 3 ms 14684 KB ok
25 Correct 3 ms 14684 KB ok
26 Correct 3 ms 14684 KB ok
27 Correct 3 ms 14684 KB ok
28 Correct 3 ms 14684 KB ok
29 Correct 3 ms 14680 KB ok
30 Correct 10 ms 64088 KB ok
31 Correct 10 ms 64092 KB ok
32 Correct 10 ms 64092 KB ok
33 Correct 9 ms 64092 KB ok
34 Correct 11 ms 64088 KB ok
35 Correct 10 ms 64092 KB ok
36 Correct 9 ms 64092 KB ok
37 Correct 10 ms 64088 KB ok
38 Correct 9 ms 64092 KB ok
39 Correct 10 ms 64036 KB ok
40 Correct 9 ms 64092 KB ok
41 Correct 10 ms 64088 KB ok
42 Execution timed out 4506 ms 1473608 KB Time limit exceeded
43 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB ok
2 Correct 1 ms 6488 KB ok
3 Correct 1 ms 6592 KB ok
4 Correct 3 ms 18780 KB ok
5 Correct 4 ms 20828 KB ok
6 Correct 1 ms 2396 KB ok
7 Correct 1 ms 6492 KB ok
8 Correct 49 ms 263508 KB ok
9 Execution timed out 4586 ms 1473368 KB Time limit exceeded
10 Halted 0 ms 0 KB -