oj.uz

Submission #930074

# Submission time Handle Problem Language Result Execution time Memory
930074 2024-02-18T12:06:48 Z abcvuitunggio Soccer Stadium (IOI23_soccer) C++17
100 / 100
 1448 ms 443956 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn=2006;
int n,ans,dp[mxn][mxn][2],l[mxn][mxn],u[mxn][mxn],d[mxn][mxn];
vector <int> ve[mxn][mxn];
vector <vector <int>> tmp;
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 (j<n-1&&!tmp[i][j+1])
        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){
    n=N,tmp=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);
            d[i][j]=n-1;
        }
    for (int j=0;j<n;j++){
        stack <int> st;
        for (int i=0;i<n;i++){
            if (F[i][j]){
                while (!st.empty()){
                    d[st.top()][j]=i-1;
                    st.pop();
                }
                continue;
            }
            while (!st.empty()&&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);
            st.push(i);
        }
        while (!st.empty())
            st.pop();
        for (int i=n-1;i>=0;i--){
            if (F[i][j]){
                while (!st.empty()){
                    u[st.top()][j]=i+1;
                    st.pop();
                }
                continue;
            }
            while (!st.empty()&&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);
            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 46 ms 132436 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 130396 KB ok
2 Correct 25 ms 130392 KB ok
3 Correct 26 ms 132444 KB ok
4 Correct 27 ms 134660 KB ok
5 Correct 25 ms 130396 KB ok
6 Correct 26 ms 132452 KB ok
7 Correct 29 ms 136984 KB ok
8 Correct 89 ms 151892 KB ok
9 Correct 1448 ms 335440 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 130396 KB ok
2 Correct 25 ms 130392 KB ok
3 Correct 25 ms 130396 KB ok
4 Correct 26 ms 132444 KB ok
5 Correct 28 ms 132632 KB ok
6 Correct 26 ms 132444 KB ok
7 Correct 26 ms 132564 KB ok
8 Correct 28 ms 132444 KB ok
9 Correct 26 ms 130392 KB ok
10 Correct 25 ms 132444 KB ok
11 Correct 26 ms 132444 KB ok
12 Correct 25 ms 132444 KB ok
13 Correct 26 ms 132444 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 132436 KB ok
2 Correct 25 ms 130396 KB ok
3 Correct 25 ms 130392 KB ok
4 Correct 25 ms 130396 KB ok
5 Correct 26 ms 132444 KB ok
6 Correct 28 ms 132632 KB ok
7 Correct 26 ms 132444 KB ok
8 Correct 26 ms 132564 KB ok
9 Correct 28 ms 132444 KB ok
10 Correct 26 ms 130392 KB ok
11 Correct 25 ms 132444 KB ok
12 Correct 26 ms 132444 KB ok
13 Correct 25 ms 132444 KB ok
14 Correct 26 ms 132444 KB ok
15 Correct 26 ms 132444 KB ok
16 Correct 26 ms 132444 KB ok
17 Correct 28 ms 132696 KB ok
18 Correct 25 ms 132444 KB ok
19 Correct 27 ms 132444 KB ok
20 Correct 29 ms 132440 KB ok
21 Correct 29 ms 132444 KB ok
22 Correct 26 ms 132444 KB ok
23 Correct 27 ms 132444 KB ok
24 Correct 26 ms 132440 KB ok
25 Correct 26 ms 132444 KB ok
26 Correct 26 ms 132444 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 132436 KB ok
2 Correct 25 ms 130396 KB ok
3 Correct 25 ms 130392 KB ok
4 Correct 26 ms 132444 KB ok
5 Correct 27 ms 134660 KB ok
6 Correct 25 ms 130396 KB ok
7 Correct 26 ms 132444 KB ok
8 Correct 28 ms 132632 KB ok
9 Correct 26 ms 132444 KB ok
10 Correct 26 ms 132564 KB ok
11 Correct 28 ms 132444 KB ok
12 Correct 26 ms 130392 KB ok
13 Correct 25 ms 132444 KB ok
14 Correct 26 ms 132444 KB ok
15 Correct 25 ms 132444 KB ok
16 Correct 26 ms 132444 KB ok
17 Correct 26 ms 132444 KB ok
18 Correct 26 ms 132444 KB ok
19 Correct 28 ms 132696 KB ok
20 Correct 25 ms 132444 KB ok
21 Correct 27 ms 132444 KB ok
22 Correct 29 ms 132440 KB ok
23 Correct 29 ms 132444 KB ok
24 Correct 26 ms 132444 KB ok
25 Correct 27 ms 132444 KB ok
26 Correct 26 ms 132440 KB ok
27 Correct 26 ms 132444 KB ok
28 Correct 26 ms 132444 KB ok
29 Correct 28 ms 132436 KB ok
30 Correct 26 ms 134492 KB ok
31 Correct 26 ms 134492 KB ok
32 Correct 27 ms 134488 KB ok
33 Correct 26 ms 134492 KB ok
34 Correct 29 ms 134480 KB ok
35 Correct 26 ms 134492 KB ok
36 Correct 26 ms 134492 KB ok
37 Correct 26 ms 134488 KB ok
38 Correct 26 ms 134744 KB ok
39 Correct 26 ms 134616 KB ok
40 Correct 26 ms 134492 KB ok
41 Correct 29 ms 134724 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 132436 KB ok
2 Correct 25 ms 130396 KB ok
3 Correct 25 ms 130392 KB ok
4 Correct 26 ms 132444 KB ok
5 Correct 27 ms 134660 KB ok
6 Correct 25 ms 130396 KB ok
7 Correct 26 ms 132444 KB ok
8 Correct 28 ms 132632 KB ok
9 Correct 26 ms 132444 KB ok
10 Correct 26 ms 132564 KB ok
11 Correct 28 ms 132444 KB ok
12 Correct 26 ms 130392 KB ok
13 Correct 25 ms 132444 KB ok
14 Correct 26 ms 132444 KB ok
15 Correct 25 ms 132444 KB ok
16 Correct 26 ms 132444 KB ok
17 Correct 26 ms 132444 KB ok
18 Correct 26 ms 132444 KB ok
19 Correct 28 ms 132696 KB ok
20 Correct 25 ms 132444 KB ok
21 Correct 27 ms 132444 KB ok
22 Correct 29 ms 132440 KB ok
23 Correct 29 ms 132444 KB ok
24 Correct 26 ms 132444 KB ok
25 Correct 27 ms 132444 KB ok
26 Correct 26 ms 132440 KB ok
27 Correct 26 ms 132444 KB ok
28 Correct 26 ms 132444 KB ok
29 Correct 28 ms 132436 KB ok
30 Correct 26 ms 134492 KB ok
31 Correct 26 ms 134492 KB ok
32 Correct 27 ms 134488 KB ok
33 Correct 26 ms 134492 KB ok
34 Correct 29 ms 134480 KB ok
35 Correct 26 ms 134492 KB ok
36 Correct 26 ms 134492 KB ok
37 Correct 26 ms 134488 KB ok
38 Correct 26 ms 134744 KB ok
39 Correct 26 ms 134616 KB ok
40 Correct 26 ms 134492 KB ok
41 Correct 29 ms 134724 KB ok
42 Correct 83 ms 152660 KB ok
43 Correct 79 ms 151800 KB ok
44 Correct 103 ms 153964 KB ok
45 Correct 84 ms 154564 KB ok
46 Correct 82 ms 153172 KB ok
47 Correct 93 ms 155984 KB ok
48 Correct 66 ms 151784 KB ok
49 Correct 68 ms 152656 KB ok
50 Correct 62 ms 150352 KB ok
51 Correct 75 ms 154964 KB ok
52 Correct 49 ms 147280 KB ok
53 Correct 46 ms 144724 KB ok
54 Correct 53 ms 147800 KB ok
55 Correct 54 ms 150096 KB ok
56 Correct 63 ms 149920 KB ok
57 Correct 82 ms 156248 KB ok
58 Correct 81 ms 156152 KB ok
59 Correct 77 ms 156244 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 132436 KB ok
2 Correct 25 ms 130396 KB ok
3 Correct 25 ms 130392 KB ok
4 Correct 26 ms 132444 KB ok
5 Correct 27 ms 134660 KB ok
6 Correct 25 ms 130396 KB ok
7 Correct 26 ms 132452 KB ok
8 Correct 29 ms 136984 KB ok
9 Correct 89 ms 151892 KB ok
10 Correct 1448 ms 335440 KB ok
11 Correct 25 ms 130396 KB ok
12 Correct 26 ms 132444 KB ok
13 Correct 28 ms 132632 KB ok
14 Correct 26 ms 132444 KB ok
15 Correct 26 ms 132564 KB ok
16 Correct 28 ms 132444 KB ok
17 Correct 26 ms 130392 KB ok
18 Correct 25 ms 132444 KB ok
19 Correct 26 ms 132444 KB ok
20 Correct 25 ms 132444 KB ok
21 Correct 26 ms 132444 KB ok
22 Correct 26 ms 132444 KB ok
23 Correct 26 ms 132444 KB ok
24 Correct 28 ms 132696 KB ok
25 Correct 25 ms 132444 KB ok
26 Correct 27 ms 132444 KB ok
27 Correct 29 ms 132440 KB ok
28 Correct 29 ms 132444 KB ok
29 Correct 26 ms 132444 KB ok
30 Correct 27 ms 132444 KB ok
31 Correct 26 ms 132440 KB ok
32 Correct 26 ms 132444 KB ok
33 Correct 26 ms 132444 KB ok
34 Correct 28 ms 132436 KB ok
35 Correct 26 ms 134492 KB ok
36 Correct 26 ms 134492 KB ok
37 Correct 27 ms 134488 KB ok
38 Correct 26 ms 134492 KB ok
39 Correct 29 ms 134480 KB ok
40 Correct 26 ms 134492 KB ok
41 Correct 26 ms 134492 KB ok
42 Correct 26 ms 134488 KB ok
43 Correct 26 ms 134744 KB ok
44 Correct 26 ms 134616 KB ok
45 Correct 26 ms 134492 KB ok
46 Correct 29 ms 134724 KB ok
47 Correct 83 ms 152660 KB ok
48 Correct 79 ms 151800 KB ok
49 Correct 103 ms 153964 KB ok
50 Correct 84 ms 154564 KB ok
51 Correct 82 ms 153172 KB ok
52 Correct 93 ms 155984 KB ok
53 Correct 66 ms 151784 KB ok
54 Correct 68 ms 152656 KB ok
55 Correct 62 ms 150352 KB ok
56 Correct 75 ms 154964 KB ok
57 Correct 49 ms 147280 KB ok
58 Correct 46 ms 144724 KB ok
59 Correct 53 ms 147800 KB ok
60 Correct 54 ms 150096 KB ok
61 Correct 63 ms 149920 KB ok
62 Correct 82 ms 156248 KB ok
63 Correct 81 ms 156152 KB ok
64 Correct 77 ms 156244 KB ok
65 Correct 1002 ms 306088 KB ok
66 Correct 531 ms 243568 KB ok
67 Correct 378 ms 230748 KB ok
68 Correct 1124 ms 338248 KB ok
69 Correct 1186 ms 322640 KB ok
70 Correct 1248 ms 319164 KB ok
71 Correct 1181 ms 346632 KB ok
72 Correct 1223 ms 355656 KB ok
73 Correct 825 ms 292228 KB ok
74 Correct 786 ms 293260 KB ok
75 Correct 804 ms 292944 KB ok
76 Correct 656 ms 260436 KB ok
77 Correct 691 ms 260180 KB ok
78 Correct 981 ms 345332 KB ok
79 Correct 366 ms 233300 KB ok
80 Correct 373 ms 233988 KB ok
81 Correct 411 ms 241576 KB ok
82 Correct 524 ms 259412 KB ok
83 Correct 508 ms 246356 KB ok
84 Correct 376 ms 232116 KB ok
85 Correct 354 ms 225512 KB ok
86 Correct 420 ms 237696 KB ok
87 Correct 424 ms 241760 KB ok
88 Correct 610 ms 267344 KB ok
89 Correct 1145 ms 342572 KB ok
90 Correct 932 ms 313460 KB ok
91 Correct 998 ms 335372 KB ok
92 Correct 394 ms 233272 KB ok
93 Correct 420 ms 234776 KB ok
94 Correct 493 ms 230868 KB ok
95 Correct 345 ms 230484 KB ok
96 Correct 343 ms 230484 KB ok
97 Correct 385 ms 230740 KB ok
98 Correct 322 ms 229356 KB ok
99 Correct 966 ms 318768 KB ok
100 Correct 1145 ms 354556 KB ok
101 Correct 1343 ms 423064 KB ok
102 Correct 1321 ms 416636 KB ok
103 Correct 1099 ms 354384 KB ok
104 Correct 1285 ms 436596 KB ok
105 Correct 1287 ms 443956 KB ok
106 Correct 1078 ms 354220 KB ok
107 Correct 1066 ms 354148 KB ok
108 Correct 1092 ms 336876 KB ok
109 Correct 1126 ms 330808 KB ok