oj.uz

Submission #930082

# Submission time Handle Problem Language Result Execution time Memory
930082 2024-02-18T12:48:54 Z abcvuitunggio Soccer Stadium (IOI23_soccer) C++17
58 / 100
 833 ms 161708 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn=2006;
int ans,dp[mxn][mxn],l[mxn][mxn],u[mxn][mxn],d[mxn][mxn],r[mxn][mxn],L[mxn],R[mxn],h[mxn][mxn],w[mxn][mxn],a[mxn][mxn];
vector <int> ve[mxn];
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=n-1;j>=0;j--){
        stack <int> st;
        for (int i=0;i<n;i++){
            if (!F[i][j])
                ve[l[i][j]].push_back(i);
            while (!st.empty()&&(F[i][j]||l[i][j]>l[st.top()][j])){
                d[st.top()][j]=i-1;
                st.pop();
            }
            L[i]=(st.empty()?-1:st.top());
            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();
            }
            R[i]=(st.empty()?-1:st.top());
            if (!F[i][j])
                st.push(i);
        }
        for (int i=0;i<n;i++){
            h[i][j]=d[i][j]-u[i][j]+1;
            w[i][j]=j-l[i][j]+1;
            a[i][j]=w[i][j]*h[i][j];
            if (r[i][j])
                dp[i][j]=max(dp[i][j+1]-w[i][j]*h[i][j+1],0);
            dp[i][j]+=a[i][j];
        }
        for (int k=0;k<=j;k++){
            for (int it=0;it<3;it++)
                for (int i:ve[k]){
                    if (L[i]>=0)
                        dp[L[i]][j]=max(dp[L[i]][j],dp[i][j]-w[L[i]][j]*h[i][j]+a[L[i]][j]);
                    if (R[i]>=0)
                        dp[R[i]][j]=max(dp[R[i]][j],dp[i][j]-w[R[i]][j]*h[i][j]+a[R[i]][j]);
                }
        }
        for (int i=0;i<n;i++)
            ve[l[i][j]].clear();
    }
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
            if (!F[i][j])
                ans=max(ans,dp[i][j]);
    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB ok
2 Correct 2 ms 12636 KB ok
3 Correct 2 ms 16728 KB ok
4 Correct 2 ms 16876 KB ok
5 Correct 2 ms 10596 KB ok
6 Correct 2 ms 14684 KB ok
7 Correct 4 ms 21596 KB ok
8 Correct 43 ms 44372 KB ok
9 Correct 781 ms 147544 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB ok
2 Correct 2 ms 12636 KB ok
3 Correct 2 ms 12636 KB ok
4 Correct 2 ms 12796 KB ok
5 Correct 2 ms 14852 KB ok
6 Correct 2 ms 12636 KB ok
7 Correct 2 ms 14684 KB ok
8 Correct 2 ms 14684 KB ok
9 Correct 2 ms 12796 KB ok
10 Correct 2 ms 12636 KB ok
11 Correct 2 ms 12632 KB ok
12 Correct 2 ms 12636 KB ok
13 Correct 2 ms 14684 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB ok
2 Correct 2 ms 12636 KB ok
3 Correct 2 ms 12636 KB ok
4 Correct 2 ms 12636 KB ok
5 Correct 2 ms 12796 KB ok
6 Correct 2 ms 14852 KB ok
7 Correct 2 ms 12636 KB ok
8 Correct 2 ms 14684 KB ok
9 Correct 2 ms 14684 KB ok
10 Correct 2 ms 12796 KB ok
11 Correct 2 ms 12636 KB ok
12 Correct 2 ms 12632 KB ok
13 Correct 2 ms 12636 KB ok
14 Correct 2 ms 14684 KB ok
15 Correct 2 ms 14684 KB ok
16 Correct 2 ms 14684 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 12892 KB ok
21 Correct 2 ms 12636 KB ok
22 Correct 2 ms 12636 KB ok
23 Correct 2 ms 12636 KB ok
24 Correct 2 ms 12636 KB ok
25 Correct 2 ms 14684 KB ok
26 Correct 2 ms 14684 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB ok
2 Correct 2 ms 12636 KB ok
3 Correct 2 ms 12636 KB ok
4 Correct 2 ms 16728 KB ok
5 Correct 2 ms 16876 KB ok
6 Correct 2 ms 12636 KB ok
7 Correct 2 ms 12796 KB ok
8 Correct 2 ms 14852 KB ok
9 Correct 2 ms 12636 KB ok
10 Correct 2 ms 14684 KB ok
11 Correct 2 ms 14684 KB ok
12 Correct 2 ms 12796 KB ok
13 Correct 2 ms 12636 KB ok
14 Correct 2 ms 12632 KB ok
15 Correct 2 ms 12636 KB ok
16 Correct 2 ms 14684 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 14684 KB ok
21 Correct 2 ms 14684 KB ok
22 Correct 2 ms 12892 KB ok
23 Correct 2 ms 12636 KB ok
24 Correct 2 ms 12636 KB ok
25 Correct 2 ms 12636 KB ok
26 Correct 2 ms 12636 KB ok
27 Correct 2 ms 14684 KB ok
28 Correct 2 ms 14684 KB ok
29 Correct 2 ms 14684 KB ok
30 Correct 3 ms 19036 KB ok
31 Correct 3 ms 19036 KB ok
32 Correct 3 ms 19036 KB ok
33 Correct 3 ms 19036 KB ok
34 Correct 2 ms 16988 KB ok
35 Correct 3 ms 16988 KB ok
36 Correct 2 ms 16988 KB ok
37 Correct 2 ms 17244 KB ok
38 Correct 2 ms 19032 KB ok
39 Correct 3 ms 16984 KB ok
40 Correct 2 ms 16988 KB ok
41 Correct 2 ms 18944 KB ok

Subtask #5
4.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB ok
2 Correct 2 ms 12636 KB ok
3 Correct 2 ms 12636 KB ok
4 Correct 2 ms 16728 KB ok
5 Correct 2 ms 16876 KB ok
6 Correct 2 ms 12636 KB ok
7 Correct 2 ms 12796 KB ok
8 Correct 2 ms 14852 KB ok
9 Correct 2 ms 12636 KB ok
10 Correct 2 ms 14684 KB ok
11 Correct 2 ms 14684 KB ok
12 Correct 2 ms 12796 KB ok
13 Correct 2 ms 12636 KB ok
14 Correct 2 ms 12632 KB ok
15 Correct 2 ms 12636 KB ok
16 Correct 2 ms 14684 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 14684 KB ok
21 Correct 2 ms 14684 KB ok
22 Correct 2 ms 12892 KB ok
23 Correct 2 ms 12636 KB ok
24 Correct 2 ms 12636 KB ok
25 Correct 2 ms 12636 KB ok
26 Correct 2 ms 12636 KB ok
27 Correct 2 ms 14684 KB ok
28 Correct 2 ms 14684 KB ok
29 Correct 2 ms 14684 KB ok
30 Correct 3 ms 19036 KB ok
31 Correct 3 ms 19036 KB ok
32 Correct 3 ms 19036 KB ok
33 Correct 3 ms 19036 KB ok
34 Correct 2 ms 16988 KB ok
35 Correct 3 ms 16988 KB ok
36 Correct 2 ms 16988 KB ok
37 Correct 2 ms 17244 KB ok
38 Correct 2 ms 19032 KB ok
39 Correct 3 ms 16984 KB ok
40 Correct 2 ms 16988 KB ok
41 Correct 2 ms 18944 KB ok
42 Correct 47 ms 46720 KB ok
43 Correct 45 ms 46876 KB ok
44 Correct 49 ms 46428 KB ok
45 Correct 57 ms 46672 KB ok
46 Correct 48 ms 46672 KB ok
47 Correct 43 ms 46416 KB ok
48 Correct 39 ms 42860 KB ok
49 Partially correct 39 ms 42836 KB partial
50 Correct 37 ms 46676 KB ok
51 Correct 51 ms 46708 KB ok
52 Correct 34 ms 41552 KB ok
53 Correct 33 ms 40908 KB ok
54 Partially correct 35 ms 41564 KB partial
55 Partially correct 34 ms 44488 KB partial
56 Correct 41 ms 40532 KB ok
57 Correct 43 ms 45292 KB ok
58 Correct 42 ms 45144 KB ok
59 Correct 41 ms 45136 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB ok
2 Correct 2 ms 12636 KB ok
3 Correct 2 ms 12636 KB ok
4 Correct 2 ms 16728 KB ok
5 Correct 2 ms 16876 KB ok
6 Correct 2 ms 10596 KB ok
7 Correct 2 ms 14684 KB ok
8 Correct 4 ms 21596 KB ok
9 Correct 43 ms 44372 KB ok
10 Correct 781 ms 147544 KB ok
11 Correct 2 ms 12636 KB ok
12 Correct 2 ms 12796 KB ok
13 Correct 2 ms 14852 KB ok
14 Correct 2 ms 12636 KB ok
15 Correct 2 ms 14684 KB ok
16 Correct 2 ms 14684 KB ok
17 Correct 2 ms 12796 KB ok
18 Correct 2 ms 12636 KB ok
19 Correct 2 ms 12632 KB ok
20 Correct 2 ms 12636 KB ok
21 Correct 2 ms 14684 KB ok
22 Correct 2 ms 14684 KB ok
23 Correct 2 ms 14684 KB ok
24 Correct 2 ms 14684 KB ok
25 Correct 2 ms 14684 KB ok
26 Correct 2 ms 14684 KB ok
27 Correct 2 ms 12892 KB ok
28 Correct 2 ms 12636 KB ok
29 Correct 2 ms 12636 KB ok
30 Correct 2 ms 12636 KB ok
31 Correct 2 ms 12636 KB ok
32 Correct 2 ms 14684 KB ok
33 Correct 2 ms 14684 KB ok
34 Correct 2 ms 14684 KB ok
35 Correct 3 ms 19036 KB ok
36 Correct 3 ms 19036 KB ok
37 Correct 3 ms 19036 KB ok
38 Correct 3 ms 19036 KB ok
39 Correct 2 ms 16988 KB ok
40 Correct 3 ms 16988 KB ok
41 Correct 2 ms 16988 KB ok
42 Correct 2 ms 17244 KB ok
43 Correct 2 ms 19032 KB ok
44 Correct 3 ms 16984 KB ok
45 Correct 2 ms 16988 KB ok
46 Correct 2 ms 18944 KB ok
47 Correct 47 ms 46720 KB ok
48 Correct 45 ms 46876 KB ok
49 Correct 49 ms 46428 KB ok
50 Correct 57 ms 46672 KB ok
51 Correct 48 ms 46672 KB ok
52 Correct 43 ms 46416 KB ok
53 Correct 39 ms 42860 KB ok
54 Partially correct 39 ms 42836 KB partial
55 Correct 37 ms 46676 KB ok
56 Correct 51 ms 46708 KB ok
57 Correct 34 ms 41552 KB ok
58 Correct 33 ms 40908 KB ok
59 Partially correct 35 ms 41564 KB partial
60 Partially correct 34 ms 44488 KB partial
61 Correct 41 ms 40532 KB ok
62 Correct 43 ms 45292 KB ok
63 Correct 42 ms 45144 KB ok
64 Correct 41 ms 45136 KB ok
65 Correct 741 ms 159896 KB ok
66 Correct 594 ms 161708 KB ok
67 Correct 517 ms 159828 KB ok
68 Correct 833 ms 157976 KB ok
69 Correct 756 ms 158092 KB ok
70 Correct 731 ms 158612 KB ok
71 Correct 791 ms 157772 KB ok
72 Correct 756 ms 157860 KB ok
73 Incorrect 624 ms 157296 KB wrong
74 Halted 0 ms 0 KB -