oj.uz

Submission #930075

# Submission time Handle Problem Language Result Execution time Memory
930075 2024-02-18T12:12:49 Z abcvuitunggio Soccer Stadium (IOI23_soccer) C++17
100 / 100
 1374 ms 424884 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn=2006;
int ans,dp[mxn][mxn][2],l[mxn][mxn],u[mxn][mxn],d[mxn][mxn],r[mxn][mxn];
vector <int> ve[mxn][mxn];
int f(int i, int j, int b){
    if (dp[i][j][b]!=-1)
        return dp[i][j][b];
    dp[i][j][b]=0;
    int sz=j-l[i][j]+1;
    for (int k:ve[i][j]){
        if (l[k][j]==l[i][j]&&((k>i)^b))
            continue;
        dp[i][j][b]=max(dp[i][j][b],f(k,j,(k>i))-sz*(d[k][j]-u[k][j]+1));
    }
    if (r[i][j])
        dp[i][j][b]=max(dp[i][j][b],max(f(i,j+1,0),f(i,j+1,1))-sz*(d[i][j+1]-u[i][j+1]+1));
    dp[i][j][b]+=sz*(d[i][j]-u[i][j]+1);
    return dp[i][j][b];
}
int biggest_stadium(int n, vector <vector <int>> F){
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++){
            l[i][j]=(j&&!F[i][j-1]?l[i][j-1]:j);
            r[i][j]=(j<n-1&&!F[i][j+1]);
            d[i][j]=n-1;
        }
    for (int j=0;j<n;j++){
        stack <int> st;
        for (int i=0;i<n;i++){
            while (!st.empty()&&(F[i][j]||l[i][j]>l[st.top()][j])){
                d[st.top()][j]=i-1;
                st.pop();
            }
            if (!st.empty())
                ve[st.top()][j].push_back(i);
            if (!F[i][j])
                st.push(i);
        }
        while (!st.empty())
            st.pop();
        for (int i=n-1;i>=0;i--){
            while (!st.empty()&&(F[i][j]||l[i][j]>l[st.top()][j])){
                u[st.top()][j]=i+1;
                st.pop();
            }
            if (!st.empty())
                ve[st.top()][j].push_back(i);
            if (!F[i][j])
                st.push(i);
        }
    }
    memset(dp,-1,sizeof(dp));
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
            if (!F[i][j])
                ans=max(ans,max(f(i,j,0),f(i,j,1)));
    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 131924 KB ok
2 Correct 26 ms 131852 KB ok
3 Correct 28 ms 136036 KB ok
4 Correct 26 ms 138072 KB ok
5 Correct 24 ms 131932 KB ok
6 Correct 25 ms 133848 KB ok
7 Correct 28 ms 140380 KB ok
8 Correct 87 ms 158288 KB ok
9 Correct 1374 ms 337396 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 131924 KB ok
2 Correct 26 ms 131852 KB ok
3 Correct 25 ms 131808 KB ok
4 Correct 27 ms 133976 KB ok
5 Correct 26 ms 133980 KB ok
6 Correct 25 ms 134024 KB ok
7 Correct 25 ms 133976 KB ok
8 Correct 28 ms 134232 KB ok
9 Correct 25 ms 131956 KB ok
10 Correct 27 ms 133784 KB ok
11 Correct 25 ms 133980 KB ok
12 Correct 25 ms 133980 KB ok
13 Correct 26 ms 133980 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 136024 KB ok
2 Correct 25 ms 131924 KB ok
3 Correct 26 ms 131852 KB ok
4 Correct 25 ms 131808 KB ok
5 Correct 27 ms 133976 KB ok
6 Correct 26 ms 133980 KB ok
7 Correct 25 ms 134024 KB ok
8 Correct 25 ms 133976 KB ok
9 Correct 28 ms 134232 KB ok
10 Correct 25 ms 131956 KB ok
11 Correct 27 ms 133784 KB ok
12 Correct 25 ms 133980 KB ok
13 Correct 25 ms 133980 KB ok
14 Correct 26 ms 133980 KB ok
15 Correct 30 ms 136024 KB ok
16 Correct 27 ms 136028 KB ok
17 Correct 25 ms 136080 KB ok
18 Correct 26 ms 136024 KB ok
19 Correct 26 ms 136028 KB ok
20 Correct 26 ms 135988 KB ok
21 Correct 27 ms 136028 KB ok
22 Correct 26 ms 136024 KB ok
23 Correct 26 ms 136028 KB ok
24 Correct 26 ms 135948 KB ok
25 Correct 26 ms 135884 KB ok
26 Correct 26 ms 136028 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 136024 KB ok
2 Correct 25 ms 131924 KB ok
3 Correct 26 ms 131852 KB ok
4 Correct 28 ms 136036 KB ok
5 Correct 26 ms 138072 KB ok
6 Correct 25 ms 131808 KB ok
7 Correct 27 ms 133976 KB ok
8 Correct 26 ms 133980 KB ok
9 Correct 25 ms 134024 KB ok
10 Correct 25 ms 133976 KB ok
11 Correct 28 ms 134232 KB ok
12 Correct 25 ms 131956 KB ok
13 Correct 27 ms 133784 KB ok
14 Correct 25 ms 133980 KB ok
15 Correct 25 ms 133980 KB ok
16 Correct 26 ms 133980 KB ok
17 Correct 30 ms 136024 KB ok
18 Correct 27 ms 136028 KB ok
19 Correct 25 ms 136080 KB ok
20 Correct 26 ms 136024 KB ok
21 Correct 26 ms 136028 KB ok
22 Correct 26 ms 135988 KB ok
23 Correct 27 ms 136028 KB ok
24 Correct 26 ms 136024 KB ok
25 Correct 26 ms 136028 KB ok
26 Correct 26 ms 135948 KB ok
27 Correct 26 ms 135884 KB ok
28 Correct 26 ms 136028 KB ok
29 Correct 28 ms 136024 KB ok
30 Correct 26 ms 138076 KB ok
31 Correct 26 ms 138088 KB ok
32 Correct 26 ms 137940 KB ok
33 Correct 29 ms 138076 KB ok
34 Correct 27 ms 138076 KB ok
35 Correct 26 ms 138060 KB ok
36 Correct 26 ms 138076 KB ok
37 Correct 27 ms 138076 KB ok
38 Correct 26 ms 138076 KB ok
39 Correct 29 ms 137988 KB ok
40 Correct 27 ms 138076 KB ok
41 Correct 26 ms 138076 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 136024 KB ok
2 Correct 25 ms 131924 KB ok
3 Correct 26 ms 131852 KB ok
4 Correct 28 ms 136036 KB ok
5 Correct 26 ms 138072 KB ok
6 Correct 25 ms 131808 KB ok
7 Correct 27 ms 133976 KB ok
8 Correct 26 ms 133980 KB ok
9 Correct 25 ms 134024 KB ok
10 Correct 25 ms 133976 KB ok
11 Correct 28 ms 134232 KB ok
12 Correct 25 ms 131956 KB ok
13 Correct 27 ms 133784 KB ok
14 Correct 25 ms 133980 KB ok
15 Correct 25 ms 133980 KB ok
16 Correct 26 ms 133980 KB ok
17 Correct 30 ms 136024 KB ok
18 Correct 27 ms 136028 KB ok
19 Correct 25 ms 136080 KB ok
20 Correct 26 ms 136024 KB ok
21 Correct 26 ms 136028 KB ok
22 Correct 26 ms 135988 KB ok
23 Correct 27 ms 136028 KB ok
24 Correct 26 ms 136024 KB ok
25 Correct 26 ms 136028 KB ok
26 Correct 26 ms 135948 KB ok
27 Correct 26 ms 135884 KB ok
28 Correct 26 ms 136028 KB ok
29 Correct 28 ms 136024 KB ok
30 Correct 26 ms 138076 KB ok
31 Correct 26 ms 138088 KB ok
32 Correct 26 ms 137940 KB ok
33 Correct 29 ms 138076 KB ok
34 Correct 27 ms 138076 KB ok
35 Correct 26 ms 138060 KB ok
36 Correct 26 ms 138076 KB ok
37 Correct 27 ms 138076 KB ok
38 Correct 26 ms 138076 KB ok
39 Correct 29 ms 137988 KB ok
40 Correct 27 ms 138076 KB ok
41 Correct 26 ms 138076 KB ok
42 Correct 82 ms 157008 KB ok
43 Correct 77 ms 156244 KB ok
44 Correct 83 ms 158700 KB ok
45 Correct 85 ms 159060 KB ok
46 Correct 83 ms 157692 KB ok
47 Correct 97 ms 160596 KB ok
48 Correct 66 ms 156408 KB ok
49 Correct 68 ms 156496 KB ok
50 Correct 62 ms 154452 KB ok
51 Correct 76 ms 158884 KB ok
52 Correct 49 ms 151376 KB ok
53 Correct 46 ms 150784 KB ok
54 Correct 51 ms 151856 KB ok
55 Correct 53 ms 153936 KB ok
56 Correct 62 ms 153456 KB ok
57 Correct 78 ms 160132 KB ok
58 Correct 82 ms 160080 KB ok
59 Correct 78 ms 160084 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 136024 KB ok
2 Correct 25 ms 131924 KB ok
3 Correct 26 ms 131852 KB ok
4 Correct 28 ms 136036 KB ok
5 Correct 26 ms 138072 KB ok
6 Correct 24 ms 131932 KB ok
7 Correct 25 ms 133848 KB ok
8 Correct 28 ms 140380 KB ok
9 Correct 87 ms 158288 KB ok
10 Correct 1374 ms 337396 KB ok
11 Correct 25 ms 131808 KB ok
12 Correct 27 ms 133976 KB ok
13 Correct 26 ms 133980 KB ok
14 Correct 25 ms 134024 KB ok
15 Correct 25 ms 133976 KB ok
16 Correct 28 ms 134232 KB ok
17 Correct 25 ms 131956 KB ok
18 Correct 27 ms 133784 KB ok
19 Correct 25 ms 133980 KB ok
20 Correct 25 ms 133980 KB ok
21 Correct 26 ms 133980 KB ok
22 Correct 30 ms 136024 KB ok
23 Correct 27 ms 136028 KB ok
24 Correct 25 ms 136080 KB ok
25 Correct 26 ms 136024 KB ok
26 Correct 26 ms 136028 KB ok
27 Correct 26 ms 135988 KB ok
28 Correct 27 ms 136028 KB ok
29 Correct 26 ms 136024 KB ok
30 Correct 26 ms 136028 KB ok
31 Correct 26 ms 135948 KB ok
32 Correct 26 ms 135884 KB ok
33 Correct 26 ms 136028 KB ok
34 Correct 28 ms 136024 KB ok
35 Correct 26 ms 138076 KB ok
36 Correct 26 ms 138088 KB ok
37 Correct 26 ms 137940 KB ok
38 Correct 29 ms 138076 KB ok
39 Correct 27 ms 138076 KB ok
40 Correct 26 ms 138060 KB ok
41 Correct 26 ms 138076 KB ok
42 Correct 27 ms 138076 KB ok
43 Correct 26 ms 138076 KB ok
44 Correct 29 ms 137988 KB ok
45 Correct 27 ms 138076 KB ok
46 Correct 26 ms 138076 KB ok
47 Correct 82 ms 157008 KB ok
48 Correct 77 ms 156244 KB ok
49 Correct 83 ms 158700 KB ok
50 Correct 85 ms 159060 KB ok
51 Correct 83 ms 157692 KB ok
52 Correct 97 ms 160596 KB ok
53 Correct 66 ms 156408 KB ok
54 Correct 68 ms 156496 KB ok
55 Correct 62 ms 154452 KB ok
56 Correct 76 ms 158884 KB ok
57 Correct 49 ms 151376 KB ok
58 Correct 46 ms 150784 KB ok
59 Correct 51 ms 151856 KB ok
60 Correct 53 ms 153936 KB ok
61 Correct 62 ms 153456 KB ok
62 Correct 78 ms 160132 KB ok
63 Correct 82 ms 160080 KB ok
64 Correct 78 ms 160084 KB ok
65 Correct 974 ms 298424 KB ok
66 Correct 534 ms 235984 KB ok
67 Correct 375 ms 222864 KB ok
68 Correct 1135 ms 330344 KB ok
69 Correct 1181 ms 314704 KB ok
70 Correct 1096 ms 311260 KB ok
71 Correct 1158 ms 338988 KB ok
72 Correct 1193 ms 347464 KB ok
73 Correct 811 ms 284292 KB ok
74 Correct 792 ms 285316 KB ok
75 Correct 829 ms 285064 KB ok
76 Correct 656 ms 252448 KB ok
77 Correct 676 ms 252500 KB ok
78 Correct 950 ms 337220 KB ok
79 Correct 376 ms 225876 KB ok
80 Correct 356 ms 225872 KB ok
81 Correct 425 ms 233768 KB ok
82 Correct 517 ms 251732 KB ok
83 Correct 516 ms 238416 KB ok
84 Correct 369 ms 224212 KB ok
85 Correct 336 ms 217728 KB ok
86 Correct 440 ms 232020 KB ok
87 Correct 418 ms 233552 KB ok
88 Correct 618 ms 261432 KB ok
89 Correct 1062 ms 334484 KB ok
90 Correct 875 ms 305540 KB ok
91 Correct 1074 ms 327760 KB ok
92 Correct 403 ms 225704 KB ok
93 Correct 414 ms 226896 KB ok
94 Correct 389 ms 222812 KB ok
95 Correct 376 ms 222592 KB ok
96 Correct 352 ms 222616 KB ok
97 Correct 336 ms 223104 KB ok
98 Correct 342 ms 221556 KB ok
99 Correct 952 ms 310776 KB ok
100 Correct 1205 ms 346504 KB ok
101 Correct 1365 ms 406312 KB ok
102 Correct 1276 ms 400980 KB ok
103 Correct 1066 ms 346668 KB ok
104 Correct 1238 ms 418388 KB ok
105 Correct 1222 ms 424884 KB ok
106 Correct 1065 ms 346684 KB ok
107 Correct 1030 ms 346424 KB ok
108 Correct 1074 ms 329264 KB ok
109 Correct 1131 ms 330780 KB ok