oj.uz

Submission #930072

# Submission time Handle Problem Language Result Execution time Memory
930072 2024-02-18T12:01:10 Z abcvuitunggio Soccer Stadium (IOI23_soccer) C++17
40.5 / 100
 1341 ms 663220 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn=2006;
int n,ans,dp[mxn][mxn],l[mxn][mxn],u[mxn][mxn],d[mxn][mxn];
vector <int> ve[mxn][mxn];
vector <vector <int>> tmp;
int f(int i, int j){
    if (dp[i][j]!=-1)
        return dp[i][j];
    dp[i][j]=0;
    int sz=j-l[i][j]+1;
    for (int k:ve[i][j])
        dp[i][j]=max(dp[i][j],f(k,j)-sz*(d[k][j]-u[k][j]+1));
    if (j<n-1&&!tmp[i][j+1])
        dp[i][j]=max(dp[i][j],f(i,j+1)-sz*(d[i][j+1]-u[i][j+1]+1));
    dp[i][j]+=sz*(d[i][j]-u[i][j]+1);
    return dp[i][j];
}
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,f(i,j));
    return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 116852 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 114780 KB ok
2 Correct 25 ms 114780 KB ok
3 Correct 24 ms 116828 KB ok
4 Correct 24 ms 118908 KB ok
5 Correct 24 ms 114776 KB ok
6 Correct 26 ms 116828 KB ok
7 Correct 28 ms 122204 KB ok
8 Correct 86 ms 157272 KB ok
9 Correct 1341 ms 663220 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 114780 KB ok
2 Correct 25 ms 114780 KB ok
3 Correct 24 ms 114828 KB ok
4 Correct 23 ms 116756 KB ok
5 Correct 24 ms 116828 KB ok
6 Correct 25 ms 116824 KB ok
7 Correct 23 ms 116828 KB ok
8 Correct 26 ms 116828 KB ok
9 Correct 26 ms 114776 KB ok
10 Correct 25 ms 116828 KB ok
11 Correct 24 ms 116824 KB ok
12 Correct 24 ms 116824 KB ok
13 Correct 24 ms 116828 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 116852 KB ok
2 Correct 26 ms 114780 KB ok
3 Correct 25 ms 114780 KB ok
4 Correct 24 ms 114828 KB ok
5 Correct 23 ms 116756 KB ok
6 Correct 24 ms 116828 KB ok
7 Correct 25 ms 116824 KB ok
8 Correct 23 ms 116828 KB ok
9 Correct 26 ms 116828 KB ok
10 Correct 26 ms 114776 KB ok
11 Correct 25 ms 116828 KB ok
12 Correct 24 ms 116824 KB ok
13 Correct 24 ms 116824 KB ok
14 Correct 24 ms 116828 KB ok
15 Correct 24 ms 116828 KB ok
16 Correct 26 ms 116860 KB ok
17 Correct 26 ms 116828 KB ok
18 Correct 24 ms 116740 KB ok
19 Correct 27 ms 116924 KB ok
20 Correct 24 ms 116828 KB ok
21 Correct 24 ms 116824 KB ok
22 Correct 24 ms 116828 KB ok
23 Correct 24 ms 116828 KB ok
24 Correct 24 ms 116860 KB ok
25 Correct 24 ms 116828 KB ok
26 Correct 27 ms 116828 KB ok

Subtask #4
4.5 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 116852 KB ok
2 Correct 26 ms 114780 KB ok
3 Correct 25 ms 114780 KB ok
4 Correct 24 ms 116828 KB ok
5 Correct 24 ms 118908 KB ok
6 Correct 24 ms 114828 KB ok
7 Correct 23 ms 116756 KB ok
8 Correct 24 ms 116828 KB ok
9 Correct 25 ms 116824 KB ok
10 Correct 23 ms 116828 KB ok
11 Correct 26 ms 116828 KB ok
12 Correct 26 ms 114776 KB ok
13 Correct 25 ms 116828 KB ok
14 Correct 24 ms 116824 KB ok
15 Correct 24 ms 116824 KB ok
16 Correct 24 ms 116828 KB ok
17 Correct 24 ms 116828 KB ok
18 Correct 26 ms 116860 KB ok
19 Correct 26 ms 116828 KB ok
20 Correct 24 ms 116740 KB ok
21 Correct 27 ms 116924 KB ok
22 Correct 24 ms 116828 KB ok
23 Correct 24 ms 116824 KB ok
24 Correct 24 ms 116828 KB ok
25 Correct 24 ms 116828 KB ok
26 Correct 24 ms 116860 KB ok
27 Correct 24 ms 116828 KB ok
28 Correct 27 ms 116828 KB ok
29 Correct 24 ms 116828 KB ok
30 Correct 24 ms 118876 KB ok
31 Correct 24 ms 118876 KB ok
32 Correct 26 ms 118876 KB ok
33 Correct 24 ms 118868 KB ok
34 Correct 25 ms 118864 KB ok
35 Correct 25 ms 118876 KB ok
36 Partially correct 25 ms 118868 KB partial
37 Correct 25 ms 118872 KB ok
38 Correct 25 ms 118852 KB ok
39 Correct 24 ms 118740 KB ok
40 Correct 25 ms 118872 KB ok
41 Correct 25 ms 118820 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 116852 KB ok
2 Correct 26 ms 114780 KB ok
3 Correct 25 ms 114780 KB ok
4 Correct 24 ms 116828 KB ok
5 Correct 24 ms 118908 KB ok
6 Correct 24 ms 114828 KB ok
7 Correct 23 ms 116756 KB ok
8 Correct 24 ms 116828 KB ok
9 Correct 25 ms 116824 KB ok
10 Correct 23 ms 116828 KB ok
11 Correct 26 ms 116828 KB ok
12 Correct 26 ms 114776 KB ok
13 Correct 25 ms 116828 KB ok
14 Correct 24 ms 116824 KB ok
15 Correct 24 ms 116824 KB ok
16 Correct 24 ms 116828 KB ok
17 Correct 24 ms 116828 KB ok
18 Correct 26 ms 116860 KB ok
19 Correct 26 ms 116828 KB ok
20 Correct 24 ms 116740 KB ok
21 Correct 27 ms 116924 KB ok
22 Correct 24 ms 116828 KB ok
23 Correct 24 ms 116824 KB ok
24 Correct 24 ms 116828 KB ok
25 Correct 24 ms 116828 KB ok
26 Correct 24 ms 116860 KB ok
27 Correct 24 ms 116828 KB ok
28 Correct 27 ms 116828 KB ok
29 Correct 24 ms 116828 KB ok
30 Correct 24 ms 118876 KB ok
31 Correct 24 ms 118876 KB ok
32 Correct 26 ms 118876 KB ok
33 Correct 24 ms 118868 KB ok
34 Correct 25 ms 118864 KB ok
35 Correct 25 ms 118876 KB ok
36 Partially correct 25 ms 118868 KB partial
37 Correct 25 ms 118872 KB ok
38 Correct 25 ms 118852 KB ok
39 Correct 24 ms 118740 KB ok
40 Correct 25 ms 118872 KB ok
41 Correct 25 ms 118820 KB ok
42 Correct 74 ms 137300 KB ok
43 Correct 78 ms 136640 KB ok
44 Correct 77 ms 138836 KB ok
45 Correct 78 ms 139492 KB ok
46 Partially correct 76 ms 138064 KB partial
47 Correct 92 ms 148464 KB ok
48 Incorrect 66 ms 136788 KB wrong
49 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 116852 KB ok
2 Correct 26 ms 114780 KB ok
3 Correct 25 ms 114780 KB ok
4 Correct 24 ms 116828 KB ok
5 Correct 24 ms 118908 KB ok
6 Correct 24 ms 114776 KB ok
7 Correct 26 ms 116828 KB ok
8 Correct 28 ms 122204 KB ok
9 Correct 86 ms 157272 KB ok
10 Correct 1341 ms 663220 KB ok
11 Correct 24 ms 114828 KB ok
12 Correct 23 ms 116756 KB ok
13 Correct 24 ms 116828 KB ok
14 Correct 25 ms 116824 KB ok
15 Correct 23 ms 116828 KB ok
16 Correct 26 ms 116828 KB ok
17 Correct 26 ms 114776 KB ok
18 Correct 25 ms 116828 KB ok
19 Correct 24 ms 116824 KB ok
20 Correct 24 ms 116824 KB ok
21 Correct 24 ms 116828 KB ok
22 Correct 24 ms 116828 KB ok
23 Correct 26 ms 116860 KB ok
24 Correct 26 ms 116828 KB ok
25 Correct 24 ms 116740 KB ok
26 Correct 27 ms 116924 KB ok
27 Correct 24 ms 116828 KB ok
28 Correct 24 ms 116824 KB ok
29 Correct 24 ms 116828 KB ok
30 Correct 24 ms 116828 KB ok
31 Correct 24 ms 116860 KB ok
32 Correct 24 ms 116828 KB ok
33 Correct 27 ms 116828 KB ok
34 Correct 24 ms 116828 KB ok
35 Correct 24 ms 118876 KB ok
36 Correct 24 ms 118876 KB ok
37 Correct 26 ms 118876 KB ok
38 Correct 24 ms 118868 KB ok
39 Correct 25 ms 118864 KB ok
40 Correct 25 ms 118876 KB ok
41 Partially correct 25 ms 118868 KB partial
42 Correct 25 ms 118872 KB ok
43 Correct 25 ms 118852 KB ok
44 Correct 24 ms 118740 KB ok
45 Correct 25 ms 118872 KB ok
46 Correct 25 ms 118820 KB ok
47 Correct 74 ms 137300 KB ok
48 Correct 78 ms 136640 KB ok
49 Correct 77 ms 138836 KB ok
50 Correct 78 ms 139492 KB ok
51 Partially correct 76 ms 138064 KB partial
52 Correct 92 ms 148464 KB ok
53 Incorrect 66 ms 136788 KB wrong
54 Halted 0 ms 0 KB -