oj.uz

Submission #930078

# Submission time Handle Problem Language Result Execution time Memory
930078 2024-02-18T12:44:14 Z abcvuitunggio Soccer Stadium (IOI23_soccer) C++17
24 / 100
 683 ms 147672 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 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]);
        }
        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 12632 KB ok
2 Correct 2 ms 12636 KB ok
3 Correct 2 ms 16988 KB ok
4 Correct 3 ms 16988 KB ok
5 Correct 2 ms 10584 KB ok
6 Correct 2 ms 14684 KB ok
7 Correct 4 ms 21596 KB ok
8 Correct 40 ms 44332 KB ok
9 Correct 683 ms 147672 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB ok
2 Correct 2 ms 12636 KB ok
3 Correct 4 ms 12636 KB ok
4 Correct 2 ms 12636 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 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 14684 KB ok

Subtask #3
5.5 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB ok
2 Correct 2 ms 12632 KB ok
3 Correct 2 ms 12636 KB ok
4 Correct 4 ms 12636 KB ok
5 Correct 2 ms 12636 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 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 14684 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 12892 KB ok
21 Correct 2 ms 12636 KB ok
22 Correct 2 ms 12892 KB ok
23 Partially correct 2 ms 12892 KB partial
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 3 ms 14684 KB ok
2 Correct 2 ms 12632 KB ok
3 Correct 2 ms 12636 KB ok
4 Correct 2 ms 16988 KB ok
5 Correct 3 ms 16988 KB ok
6 Correct 4 ms 12636 KB ok
7 Correct 2 ms 12636 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 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 14684 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 12892 KB ok
23 Correct 2 ms 12636 KB ok
24 Correct 2 ms 12892 KB ok
25 Partially correct 2 ms 12892 KB partial
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 2 ms 19036 KB ok
31 Correct 2 ms 19036 KB ok
32 Correct 2 ms 19032 KB ok
33 Correct 3 ms 19032 KB ok
34 Correct 3 ms 16984 KB ok
35 Correct 2 ms 16988 KB ok
36 Partially correct 2 ms 17140 KB partial
37 Partially correct 2 ms 16988 KB partial
38 Correct 2 ms 19036 KB ok
39 Correct 2 ms 16984 KB ok
40 Correct 2 ms 16984 KB ok
41 Correct 2 ms 19036 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB ok
2 Correct 2 ms 12632 KB ok
3 Correct 2 ms 12636 KB ok
4 Correct 2 ms 16988 KB ok
5 Correct 3 ms 16988 KB ok
6 Correct 4 ms 12636 KB ok
7 Correct 2 ms 12636 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 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 14684 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 12892 KB ok
23 Correct 2 ms 12636 KB ok
24 Correct 2 ms 12892 KB ok
25 Partially correct 2 ms 12892 KB partial
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 2 ms 19036 KB ok
31 Correct 2 ms 19036 KB ok
32 Correct 2 ms 19032 KB ok
33 Correct 3 ms 19032 KB ok
34 Correct 3 ms 16984 KB ok
35 Correct 2 ms 16988 KB ok
36 Partially correct 2 ms 17140 KB partial
37 Partially correct 2 ms 16988 KB partial
38 Correct 2 ms 19036 KB ok
39 Correct 2 ms 16984 KB ok
40 Correct 2 ms 16984 KB ok
41 Correct 2 ms 19036 KB ok
42 Partially correct 38 ms 46684 KB partial
43 Correct 38 ms 46796 KB ok
44 Correct 36 ms 46476 KB ok
45 Correct 39 ms 46428 KB ok
46 Partially correct 40 ms 46676 KB partial
47 Correct 33 ms 46424 KB ok
48 Incorrect 34 ms 42848 KB wrong
49 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB ok
2 Correct 2 ms 12632 KB ok
3 Correct 2 ms 12636 KB ok
4 Correct 2 ms 16988 KB ok
5 Correct 3 ms 16988 KB ok
6 Correct 2 ms 10584 KB ok
7 Correct 2 ms 14684 KB ok
8 Correct 4 ms 21596 KB ok
9 Correct 40 ms 44332 KB ok
10 Correct 683 ms 147672 KB ok
11 Correct 4 ms 12636 KB ok
12 Correct 2 ms 12636 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 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 14684 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 12892 KB ok
28 Correct 2 ms 12636 KB ok
29 Correct 2 ms 12892 KB ok
30 Partially correct 2 ms 12892 KB partial
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 2 ms 19036 KB ok
36 Correct 2 ms 19036 KB ok
37 Correct 2 ms 19032 KB ok
38 Correct 3 ms 19032 KB ok
39 Correct 3 ms 16984 KB ok
40 Correct 2 ms 16988 KB ok
41 Partially correct 2 ms 17140 KB partial
42 Partially correct 2 ms 16988 KB partial
43 Correct 2 ms 19036 KB ok
44 Correct 2 ms 16984 KB ok
45 Correct 2 ms 16984 KB ok
46 Correct 2 ms 19036 KB ok
47 Partially correct 38 ms 46684 KB partial
48 Correct 38 ms 46796 KB ok
49 Correct 36 ms 46476 KB ok
50 Correct 39 ms 46428 KB ok
51 Partially correct 40 ms 46676 KB partial
52 Correct 33 ms 46424 KB ok
53 Incorrect 34 ms 42848 KB wrong
54 Halted 0 ms 0 KB -