oj.uz

Submission #930081

# Submission time Handle Problem Language Result Execution time Memory
930081 2024-02-18T12:47:43 Z abcvuitunggio Soccer Stadium (IOI23_soccer) C++17
54 / 100
 717 ms 147904 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<2;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 2 ms 14684 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB ok
2 Correct 2 ms 12780 KB ok
3 Correct 2 ms 16732 KB ok
4 Correct 2 ms 16988 KB ok
5 Correct 2 ms 10840 KB ok
6 Correct 2 ms 14684 KB ok
7 Correct 4 ms 21588 KB ok
8 Correct 37 ms 44504 KB ok
9 Correct 717 ms 147904 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB ok
2 Correct 2 ms 12780 KB ok
3 Correct 2 ms 12636 KB ok
4 Correct 2 ms 12800 KB ok
5 Correct 2 ms 14684 KB ok
6 Correct 2 ms 12636 KB ok
7 Correct 2 ms 14684 KB ok
8 Correct 3 ms 14684 KB ok
9 Correct 2 ms 12636 KB ok
10 Correct 2 ms 12636 KB ok
11 Correct 2 ms 12636 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 2 ms 14684 KB ok
2 Correct 2 ms 12888 KB ok
3 Correct 2 ms 12780 KB ok
4 Correct 2 ms 12636 KB ok
5 Correct 2 ms 12800 KB ok
6 Correct 2 ms 14684 KB ok
7 Correct 2 ms 12636 KB ok
8 Correct 2 ms 14684 KB ok
9 Correct 3 ms 14684 KB ok
10 Correct 2 ms 12636 KB ok
11 Correct 2 ms 12636 KB ok
12 Correct 2 ms 12636 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 14680 KB ok
20 Correct 2 ms 12892 KB ok
21 Correct 1 ms 12636 KB ok
22 Correct 2 ms 12712 KB ok
23 Correct 1 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 2 ms 14684 KB ok
2 Correct 2 ms 12888 KB ok
3 Correct 2 ms 12780 KB ok
4 Correct 2 ms 16732 KB ok
5 Correct 2 ms 16988 KB ok
6 Correct 2 ms 12636 KB ok
7 Correct 2 ms 12800 KB ok
8 Correct 2 ms 14684 KB ok
9 Correct 2 ms 12636 KB ok
10 Correct 2 ms 14684 KB ok
11 Correct 3 ms 14684 KB ok
12 Correct 2 ms 12636 KB ok
13 Correct 2 ms 12636 KB ok
14 Correct 2 ms 12636 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 14680 KB ok
22 Correct 2 ms 12892 KB ok
23 Correct 1 ms 12636 KB ok
24 Correct 2 ms 12712 KB ok
25 Correct 1 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 19032 KB ok
31 Correct 3 ms 19032 KB ok
32 Correct 2 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 16988 KB ok
38 Correct 2 ms 19036 KB ok
39 Correct 2 ms 16984 KB ok
40 Correct 2 ms 16988 KB ok
41 Correct 3 ms 19036 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB ok
2 Correct 2 ms 12888 KB ok
3 Correct 2 ms 12780 KB ok
4 Correct 2 ms 16732 KB ok
5 Correct 2 ms 16988 KB ok
6 Correct 2 ms 12636 KB ok
7 Correct 2 ms 12800 KB ok
8 Correct 2 ms 14684 KB ok
9 Correct 2 ms 12636 KB ok
10 Correct 2 ms 14684 KB ok
11 Correct 3 ms 14684 KB ok
12 Correct 2 ms 12636 KB ok
13 Correct 2 ms 12636 KB ok
14 Correct 2 ms 12636 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 14680 KB ok
22 Correct 2 ms 12892 KB ok
23 Correct 1 ms 12636 KB ok
24 Correct 2 ms 12712 KB ok
25 Correct 1 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 19032 KB ok
31 Correct 3 ms 19032 KB ok
32 Correct 2 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 16988 KB ok
38 Correct 2 ms 19036 KB ok
39 Correct 2 ms 16984 KB ok
40 Correct 2 ms 16988 KB ok
41 Correct 3 ms 19036 KB ok
42 Correct 42 ms 46672 KB ok
43 Correct 44 ms 46872 KB ok
44 Correct 43 ms 46560 KB ok
45 Correct 40 ms 46584 KB ok
46 Correct 43 ms 46676 KB ok
47 Correct 41 ms 46416 KB ok
48 Incorrect 36 ms 42844 KB wrong
49 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB ok
2 Correct 2 ms 12888 KB ok
3 Correct 2 ms 12780 KB ok
4 Correct 2 ms 16732 KB ok
5 Correct 2 ms 16988 KB ok
6 Correct 2 ms 10840 KB ok
7 Correct 2 ms 14684 KB ok
8 Correct 4 ms 21588 KB ok
9 Correct 37 ms 44504 KB ok
10 Correct 717 ms 147904 KB ok
11 Correct 2 ms 12636 KB ok
12 Correct 2 ms 12800 KB ok
13 Correct 2 ms 14684 KB ok
14 Correct 2 ms 12636 KB ok
15 Correct 2 ms 14684 KB ok
16 Correct 3 ms 14684 KB ok
17 Correct 2 ms 12636 KB ok
18 Correct 2 ms 12636 KB ok
19 Correct 2 ms 12636 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 14680 KB ok
27 Correct 2 ms 12892 KB ok
28 Correct 1 ms 12636 KB ok
29 Correct 2 ms 12712 KB ok
30 Correct 1 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 19032 KB ok
36 Correct 3 ms 19032 KB ok
37 Correct 2 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 16988 KB ok
43 Correct 2 ms 19036 KB ok
44 Correct 2 ms 16984 KB ok
45 Correct 2 ms 16988 KB ok
46 Correct 3 ms 19036 KB ok
47 Correct 42 ms 46672 KB ok
48 Correct 44 ms 46872 KB ok
49 Correct 43 ms 46560 KB ok
50 Correct 40 ms 46584 KB ok
51 Correct 43 ms 46676 KB ok
52 Correct 41 ms 46416 KB ok
53 Incorrect 36 ms 42844 KB wrong
54 Halted 0 ms 0 KB -