oj.uz

Submission #930065

# Submission time Handle Problem Language Result Execution time Memory
930065 2024-02-18T11:50:37 Z abcvuitunggio Soccer Stadium (IOI23_soccer) C++17
19.5 / 100
 422 ms 246528 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn=2006;
int n,res,dp[mxn][mxn],l[mxn][mxn],u[mxn][mxn],d[mxn][mxn],ch[mxn][mxn],a[mxn][mxn],b[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;
        }
    memset(a,-1,sizeof(a));
    memset(b,-1,sizeof(b));
    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()){
                if (l[i][j]==l[st.top()][j]){
                    a[i][j]=st.top();
                    continue;
                }
                ve[st.top()][j].push_back(i);
            }
            ch[i][j]=1;
            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()){
                if (l[i][j]==l[st.top()][j]){
                    b[i][j]=st.top();
                    continue;
                }
                ve[st.top()][j].push_back(i);
            }
            ch[i][j]=1;
            st.push(i);
        }
    }
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++){
            if (a[i][j]>=0)
                d[i][j]=d[a[i][j]][j];
            if (b[i][j]>=0)
                u[i][j]=u[b[i][j]][j];
        }
    memset(dp,-1,sizeof(dp));
    int ans=0;
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
            if (ch[i][j])
                ans=max(ans,f(i,j));
    return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 151636 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 149596 KB ok
2 Correct 29 ms 149596 KB ok
3 Correct 28 ms 151636 KB ok
4 Correct 31 ms 151840 KB ok
5 Correct 28 ms 147724 KB ok
6 Correct 28 ms 151644 KB ok
7 Correct 29 ms 154020 KB ok
8 Correct 49 ms 169476 KB ok
9 Correct 422 ms 246528 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 149596 KB ok
2 Correct 29 ms 149596 KB ok
3 Correct 28 ms 149592 KB ok
4 Correct 28 ms 151644 KB ok
5 Correct 29 ms 151644 KB ok
6 Correct 28 ms 151644 KB ok
7 Correct 30 ms 152068 KB ok
8 Correct 28 ms 151632 KB ok
9 Correct 27 ms 149588 KB ok
10 Correct 28 ms 151644 KB ok
11 Correct 29 ms 151644 KB ok
12 Correct 29 ms 151644 KB ok
13 Correct 28 ms 151636 KB ok

Subtask #3
5.5 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 151636 KB ok
2 Correct 28 ms 149596 KB ok
3 Correct 29 ms 149596 KB ok
4 Correct 28 ms 149592 KB ok
5 Correct 28 ms 151644 KB ok
6 Correct 29 ms 151644 KB ok
7 Correct 28 ms 151644 KB ok
8 Correct 30 ms 152068 KB ok
9 Correct 28 ms 151632 KB ok
10 Correct 27 ms 149588 KB ok
11 Correct 28 ms 151644 KB ok
12 Correct 29 ms 151644 KB ok
13 Correct 29 ms 151644 KB ok
14 Correct 28 ms 151636 KB ok
15 Correct 29 ms 151636 KB ok
16 Partially correct 28 ms 151644 KB partial
17 Correct 30 ms 151604 KB ok
18 Correct 30 ms 151640 KB ok
19 Correct 29 ms 151644 KB ok
20 Correct 29 ms 151644 KB ok
21 Correct 29 ms 151644 KB ok
22 Partially correct 31 ms 151900 KB partial
23 Correct 30 ms 151628 KB ok
24 Partially correct 28 ms 151644 KB partial
25 Correct 28 ms 151644 KB ok
26 Correct 30 ms 151644 KB ok

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 151636 KB ok
2 Correct 28 ms 149596 KB ok
3 Correct 29 ms 149596 KB ok
4 Correct 28 ms 151636 KB ok
5 Correct 31 ms 151840 KB ok
6 Correct 28 ms 149592 KB ok
7 Correct 28 ms 151644 KB ok
8 Correct 29 ms 151644 KB ok
9 Correct 28 ms 151644 KB ok
10 Correct 30 ms 152068 KB ok
11 Correct 28 ms 151632 KB ok
12 Correct 27 ms 149588 KB ok
13 Correct 28 ms 151644 KB ok
14 Correct 29 ms 151644 KB ok
15 Correct 29 ms 151644 KB ok
16 Correct 28 ms 151636 KB ok
17 Correct 29 ms 151636 KB ok
18 Partially correct 28 ms 151644 KB partial
19 Correct 30 ms 151604 KB ok
20 Correct 30 ms 151640 KB ok
21 Correct 29 ms 151644 KB ok
22 Correct 29 ms 151644 KB ok
23 Correct 29 ms 151644 KB ok
24 Partially correct 31 ms 151900 KB partial
25 Correct 30 ms 151628 KB ok
26 Partially correct 28 ms 151644 KB partial
27 Correct 28 ms 151644 KB ok
28 Correct 30 ms 151644 KB ok
29 Partially correct 28 ms 151644 KB partial
30 Partially correct 28 ms 151756 KB partial
31 Correct 30 ms 151636 KB ok
32 Correct 28 ms 151644 KB ok
33 Correct 29 ms 151644 KB ok
34 Incorrect 28 ms 151644 KB wrong
35 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 151636 KB ok
2 Correct 28 ms 149596 KB ok
3 Correct 29 ms 149596 KB ok
4 Correct 28 ms 151636 KB ok
5 Correct 31 ms 151840 KB ok
6 Correct 28 ms 149592 KB ok
7 Correct 28 ms 151644 KB ok
8 Correct 29 ms 151644 KB ok
9 Correct 28 ms 151644 KB ok
10 Correct 30 ms 152068 KB ok
11 Correct 28 ms 151632 KB ok
12 Correct 27 ms 149588 KB ok
13 Correct 28 ms 151644 KB ok
14 Correct 29 ms 151644 KB ok
15 Correct 29 ms 151644 KB ok
16 Correct 28 ms 151636 KB ok
17 Correct 29 ms 151636 KB ok
18 Partially correct 28 ms 151644 KB partial
19 Correct 30 ms 151604 KB ok
20 Correct 30 ms 151640 KB ok
21 Correct 29 ms 151644 KB ok
22 Correct 29 ms 151644 KB ok
23 Correct 29 ms 151644 KB ok
24 Partially correct 31 ms 151900 KB partial
25 Correct 30 ms 151628 KB ok
26 Partially correct 28 ms 151644 KB partial
27 Correct 28 ms 151644 KB ok
28 Correct 30 ms 151644 KB ok
29 Partially correct 28 ms 151644 KB partial
30 Partially correct 28 ms 151756 KB partial
31 Correct 30 ms 151636 KB ok
32 Correct 28 ms 151644 KB ok
33 Correct 29 ms 151644 KB ok
34 Incorrect 28 ms 151644 KB wrong
35 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 151636 KB ok
2 Correct 28 ms 149596 KB ok
3 Correct 29 ms 149596 KB ok
4 Correct 28 ms 151636 KB ok
5 Correct 31 ms 151840 KB ok
6 Correct 28 ms 147724 KB ok
7 Correct 28 ms 151644 KB ok
8 Correct 29 ms 154020 KB ok
9 Correct 49 ms 169476 KB ok
10 Correct 422 ms 246528 KB ok
11 Correct 28 ms 149592 KB ok
12 Correct 28 ms 151644 KB ok
13 Correct 29 ms 151644 KB ok
14 Correct 28 ms 151644 KB ok
15 Correct 30 ms 152068 KB ok
16 Correct 28 ms 151632 KB ok
17 Correct 27 ms 149588 KB ok
18 Correct 28 ms 151644 KB ok
19 Correct 29 ms 151644 KB ok
20 Correct 29 ms 151644 KB ok
21 Correct 28 ms 151636 KB ok
22 Correct 29 ms 151636 KB ok
23 Partially correct 28 ms 151644 KB partial
24 Correct 30 ms 151604 KB ok
25 Correct 30 ms 151640 KB ok
26 Correct 29 ms 151644 KB ok
27 Correct 29 ms 151644 KB ok
28 Correct 29 ms 151644 KB ok
29 Partially correct 31 ms 151900 KB partial
30 Correct 30 ms 151628 KB ok
31 Partially correct 28 ms 151644 KB partial
32 Correct 28 ms 151644 KB ok
33 Correct 30 ms 151644 KB ok
34 Partially correct 28 ms 151644 KB partial
35 Partially correct 28 ms 151756 KB partial
36 Correct 30 ms 151636 KB ok
37 Correct 28 ms 151644 KB ok
38 Correct 29 ms 151644 KB ok
39 Incorrect 28 ms 151644 KB wrong
40 Halted 0 ms 0 KB -