oj.uz

Submission #930086

# Submission time Handle Problem Language Result Execution time Memory
930086 2024-02-18T12:52:17 Z abcvuitunggio Soccer Stadium (IOI23_soccer) C++17
24 / 100
 763 ms 147684 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]);
                reverse(ve[k].begin(),ve[k].end());
                for (int i:ve[k])
                    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]);
                reverse(ve[k].begin(),ve[k].end());
            }
        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 12636 KB ok
2 Correct 2 ms 12636 KB ok
3 Correct 2 ms 16732 KB ok
4 Correct 2 ms 16988 KB ok
5 Correct 1 ms 10596 KB ok
6 Correct 2 ms 14684 KB ok
7 Correct 4 ms 21596 KB ok
8 Correct 39 ms 44820 KB ok
9 Correct 763 ms 147684 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 12632 KB ok
4 Correct 2 ms 12636 KB ok
5 Correct 2 ms 14936 KB ok
6 Correct 2 ms 12804 KB ok
7 Correct 2 ms 14684 KB ok
8 Correct 2 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 14836 KB ok

Subtask #3
5.5 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB ok
2 Correct 2 ms 12636 KB ok
3 Correct 2 ms 12636 KB ok
4 Correct 2 ms 12632 KB ok
5 Correct 2 ms 12636 KB ok
6 Correct 2 ms 14936 KB ok
7 Correct 2 ms 12804 KB ok
8 Correct 2 ms 14684 KB ok
9 Correct 2 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 14836 KB ok
15 Correct 2 ms 14684 KB ok
16 Partially correct 2 ms 14684 KB partial
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 12636 KB ok
21 Correct 2 ms 12636 KB ok
22 Correct 2 ms 12632 KB ok
23 Correct 2 ms 13144 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
4.5 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB ok
2 Correct 2 ms 12636 KB ok
3 Correct 2 ms 12636 KB ok
4 Correct 2 ms 16732 KB ok
5 Correct 2 ms 16988 KB ok
6 Correct 2 ms 12632 KB ok
7 Correct 2 ms 12636 KB ok
8 Correct 2 ms 14936 KB ok
9 Correct 2 ms 12804 KB ok
10 Correct 2 ms 14684 KB ok
11 Correct 2 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 14836 KB ok
17 Correct 2 ms 14684 KB ok
18 Partially correct 2 ms 14684 KB partial
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 12636 KB ok
23 Correct 2 ms 12636 KB ok
24 Correct 2 ms 12632 KB ok
25 Correct 2 ms 13144 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 14680 KB ok
30 Correct 3 ms 19032 KB ok
31 Correct 3 ms 19036 KB ok
32 Correct 2 ms 19032 KB ok
33 Correct 2 ms 19036 KB ok
34 Correct 2 ms 17160 KB ok
35 Correct 2 ms 16988 KB ok
36 Correct 2 ms 16984 KB ok
37 Correct 2 ms 16988 KB ok
38 Correct 3 ms 19036 KB ok
39 Correct 2 ms 16988 KB ok
40 Correct 2 ms 16988 KB ok
41 Correct 2 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 12636 KB ok
3 Correct 2 ms 12636 KB ok
4 Correct 2 ms 16732 KB ok
5 Correct 2 ms 16988 KB ok
6 Correct 2 ms 12632 KB ok
7 Correct 2 ms 12636 KB ok
8 Correct 2 ms 14936 KB ok
9 Correct 2 ms 12804 KB ok
10 Correct 2 ms 14684 KB ok
11 Correct 2 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 14836 KB ok
17 Correct 2 ms 14684 KB ok
18 Partially correct 2 ms 14684 KB partial
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 12636 KB ok
23 Correct 2 ms 12636 KB ok
24 Correct 2 ms 12632 KB ok
25 Correct 2 ms 13144 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 14680 KB ok
30 Correct 3 ms 19032 KB ok
31 Correct 3 ms 19036 KB ok
32 Correct 2 ms 19032 KB ok
33 Correct 2 ms 19036 KB ok
34 Correct 2 ms 17160 KB ok
35 Correct 2 ms 16988 KB ok
36 Correct 2 ms 16984 KB ok
37 Correct 2 ms 16988 KB ok
38 Correct 3 ms 19036 KB ok
39 Correct 2 ms 16988 KB ok
40 Correct 2 ms 16988 KB ok
41 Correct 2 ms 19036 KB ok
42 Correct 41 ms 46740 KB ok
43 Correct 41 ms 46676 KB ok
44 Correct 39 ms 46420 KB ok
45 Correct 39 ms 46420 KB ok
46 Correct 49 ms 46704 KB ok
47 Correct 34 ms 46416 KB ok
48 Incorrect 37 ms 42836 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 12636 KB ok
3 Correct 2 ms 12636 KB ok
4 Correct 2 ms 16732 KB ok
5 Correct 2 ms 16988 KB ok
6 Correct 1 ms 10596 KB ok
7 Correct 2 ms 14684 KB ok
8 Correct 4 ms 21596 KB ok
9 Correct 39 ms 44820 KB ok
10 Correct 763 ms 147684 KB ok
11 Correct 2 ms 12632 KB ok
12 Correct 2 ms 12636 KB ok
13 Correct 2 ms 14936 KB ok
14 Correct 2 ms 12804 KB ok
15 Correct 2 ms 14684 KB ok
16 Correct 2 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 14836 KB ok
22 Correct 2 ms 14684 KB ok
23 Partially correct 2 ms 14684 KB partial
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 12636 KB ok
28 Correct 2 ms 12636 KB ok
29 Correct 2 ms 12632 KB ok
30 Correct 2 ms 13144 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 14680 KB ok
35 Correct 3 ms 19032 KB ok
36 Correct 3 ms 19036 KB ok
37 Correct 2 ms 19032 KB ok
38 Correct 2 ms 19036 KB ok
39 Correct 2 ms 17160 KB ok
40 Correct 2 ms 16988 KB ok
41 Correct 2 ms 16984 KB ok
42 Correct 2 ms 16988 KB ok
43 Correct 3 ms 19036 KB ok
44 Correct 2 ms 16988 KB ok
45 Correct 2 ms 16988 KB ok
46 Correct 2 ms 19036 KB ok
47 Correct 41 ms 46740 KB ok
48 Correct 41 ms 46676 KB ok
49 Correct 39 ms 46420 KB ok
50 Correct 39 ms 46420 KB ok
51 Correct 49 ms 46704 KB ok
52 Correct 34 ms 46416 KB ok
53 Incorrect 37 ms 42836 KB wrong
54 Halted 0 ms 0 KB -