oj.uz

Submission #929976

# Submission time Handle Problem Language Result Execution time Memory
929976 2024-02-18T08:54:56 Z abcvuitunggio Soccer Stadium (IOI23_soccer) C++17
18 / 100
 1149 ms 344052 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn=2006;
int n,ans,dp[mxn][mxn],l[mxn][mxn],r[mxn][mxn],u[mxn][mxn],d[mxn][mxn],ch[mxn][mxn];
vector <int> ve[mxn][mxn];
int f(int i, int j){
    if (dp[i][j]!=-1)
        return dp[i][j];
    if (j!=l[i][j])
        return dp[i][j]=f(i,l[i][j]);
    dp[i][j]=0;
    int sz=r[i][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));
    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;
    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=n;j;j--)
            r[i][j-1]=(j<n&&!F[i][j]?r[i][j]:j-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]||r[i][j]<r[st.top()][j])){
                d[st.top()][j]=i-1;
                st.pop();
            }
            if (!st.empty())
                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]||r[i][j]<r[st.top()][j])){
                u[st.top()][j]=i+1;
                st.pop();
            }
            if (!st.empty())
                ve[st.top()][j].push_back(i);
            ch[i][j]=1;
            st.push(i);
        }
    }
    memset(dp,-1,sizeof(dp));
    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 32 ms 121688 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 117540 KB ok
2 Correct 28 ms 117584 KB ok
3 Correct 30 ms 121692 KB ok
4 Correct 33 ms 123736 KB ok
5 Correct 32 ms 117596 KB ok
6 Correct 32 ms 119632 KB ok
7 Correct 30 ms 128084 KB ok
8 Correct 80 ms 148444 KB ok
9 Correct 1149 ms 344052 KB ok

Subtask #2
2.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 117540 KB ok
2 Correct 28 ms 117584 KB ok
3 Correct 35 ms 117584 KB ok
4 Correct 35 ms 119456 KB ok
5 Correct 32 ms 119636 KB ok
6 Correct 32 ms 119644 KB ok
7 Partially correct 28 ms 119484 KB partial
8 Correct 25 ms 119544 KB ok
9 Correct 30 ms 117452 KB ok
10 Correct 30 ms 119500 KB ok
11 Correct 32 ms 119520 KB ok
12 Correct 32 ms 119492 KB ok
13 Correct 29 ms 119644 KB ok

Subtask #3
5.5 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 121688 KB ok
2 Correct 30 ms 117540 KB ok
3 Correct 28 ms 117584 KB ok
4 Correct 35 ms 117584 KB ok
5 Correct 35 ms 119456 KB ok
6 Correct 32 ms 119636 KB ok
7 Correct 32 ms 119644 KB ok
8 Partially correct 28 ms 119484 KB partial
9 Correct 25 ms 119544 KB ok
10 Correct 30 ms 117452 KB ok
11 Correct 30 ms 119500 KB ok
12 Correct 32 ms 119520 KB ok
13 Correct 32 ms 119492 KB ok
14 Correct 29 ms 119644 KB ok
15 Correct 30 ms 121688 KB ok
16 Partially correct 29 ms 121876 KB partial
17 Partially correct 30 ms 121688 KB partial
18 Correct 36 ms 121624 KB ok
19 Correct 27 ms 121692 KB ok
20 Correct 26 ms 121552 KB ok
21 Correct 30 ms 121596 KB ok
22 Correct 30 ms 121692 KB ok
23 Correct 28 ms 121648 KB ok
24 Partially correct 32 ms 121692 KB partial
25 Partially correct 29 ms 121624 KB partial
26 Partially correct 30 ms 121544 KB partial

Subtask #4
4.5 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 121688 KB ok
2 Correct 30 ms 117540 KB ok
3 Correct 28 ms 117584 KB ok
4 Correct 30 ms 121692 KB ok
5 Correct 33 ms 123736 KB ok
6 Correct 35 ms 117584 KB ok
7 Correct 35 ms 119456 KB ok
8 Correct 32 ms 119636 KB ok
9 Correct 32 ms 119644 KB ok
10 Partially correct 28 ms 119484 KB partial
11 Correct 25 ms 119544 KB ok
12 Correct 30 ms 117452 KB ok
13 Correct 30 ms 119500 KB ok
14 Correct 32 ms 119520 KB ok
15 Correct 32 ms 119492 KB ok
16 Correct 29 ms 119644 KB ok
17 Correct 30 ms 121688 KB ok
18 Partially correct 29 ms 121876 KB partial
19 Partially correct 30 ms 121688 KB partial
20 Correct 36 ms 121624 KB ok
21 Correct 27 ms 121692 KB ok
22 Correct 26 ms 121552 KB ok
23 Correct 30 ms 121596 KB ok
24 Correct 30 ms 121692 KB ok
25 Correct 28 ms 121648 KB ok
26 Partially correct 32 ms 121692 KB partial
27 Partially correct 29 ms 121624 KB partial
28 Partially correct 30 ms 121544 KB partial
29 Partially correct 32 ms 121664 KB partial
30 Correct 35 ms 123680 KB ok
31 Correct 35 ms 123732 KB ok
32 Correct 33 ms 123732 KB ok
33 Correct 27 ms 123680 KB ok
34 Correct 28 ms 123708 KB ok
35 Correct 27 ms 123648 KB ok
36 Correct 26 ms 123728 KB ok
37 Partially correct 26 ms 123612 KB partial
38 Partially correct 27 ms 123740 KB partial
39 Partially correct 27 ms 123544 KB partial
40 Correct 27 ms 123600 KB ok
41 Partially correct 27 ms 123684 KB partial

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 121688 KB ok
2 Correct 30 ms 117540 KB ok
3 Correct 28 ms 117584 KB ok
4 Correct 30 ms 121692 KB ok
5 Correct 33 ms 123736 KB ok
6 Correct 35 ms 117584 KB ok
7 Correct 35 ms 119456 KB ok
8 Correct 32 ms 119636 KB ok
9 Correct 32 ms 119644 KB ok
10 Partially correct 28 ms 119484 KB partial
11 Correct 25 ms 119544 KB ok
12 Correct 30 ms 117452 KB ok
13 Correct 30 ms 119500 KB ok
14 Correct 32 ms 119520 KB ok
15 Correct 32 ms 119492 KB ok
16 Correct 29 ms 119644 KB ok
17 Correct 30 ms 121688 KB ok
18 Partially correct 29 ms 121876 KB partial
19 Partially correct 30 ms 121688 KB partial
20 Correct 36 ms 121624 KB ok
21 Correct 27 ms 121692 KB ok
22 Correct 26 ms 121552 KB ok
23 Correct 30 ms 121596 KB ok
24 Correct 30 ms 121692 KB ok
25 Correct 28 ms 121648 KB ok
26 Partially correct 32 ms 121692 KB partial
27 Partially correct 29 ms 121624 KB partial
28 Partially correct 30 ms 121544 KB partial
29 Partially correct 32 ms 121664 KB partial
30 Correct 35 ms 123680 KB ok
31 Correct 35 ms 123732 KB ok
32 Correct 33 ms 123732 KB ok
33 Correct 27 ms 123680 KB ok
34 Correct 28 ms 123708 KB ok
35 Correct 27 ms 123648 KB ok
36 Correct 26 ms 123728 KB ok
37 Partially correct 26 ms 123612 KB partial
38 Partially correct 27 ms 123740 KB partial
39 Partially correct 27 ms 123544 KB partial
40 Correct 27 ms 123600 KB ok
41 Partially correct 27 ms 123684 KB partial
42 Partially correct 75 ms 145624 KB partial
43 Partially correct 74 ms 145232 KB partial
44 Partially correct 72 ms 146336 KB partial
45 Partially correct 69 ms 147116 KB partial
46 Partially correct 67 ms 145856 KB partial
47 Partially correct 97 ms 150456 KB partial
48 Incorrect 82 ms 145976 KB wrong
49 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 121688 KB ok
2 Correct 30 ms 117540 KB ok
3 Correct 28 ms 117584 KB ok
4 Correct 30 ms 121692 KB ok
5 Correct 33 ms 123736 KB ok
6 Correct 32 ms 117596 KB ok
7 Correct 32 ms 119632 KB ok
8 Correct 30 ms 128084 KB ok
9 Correct 80 ms 148444 KB ok
10 Correct 1149 ms 344052 KB ok
11 Correct 35 ms 117584 KB ok
12 Correct 35 ms 119456 KB ok
13 Correct 32 ms 119636 KB ok
14 Correct 32 ms 119644 KB ok
15 Partially correct 28 ms 119484 KB partial
16 Correct 25 ms 119544 KB ok
17 Correct 30 ms 117452 KB ok
18 Correct 30 ms 119500 KB ok
19 Correct 32 ms 119520 KB ok
20 Correct 32 ms 119492 KB ok
21 Correct 29 ms 119644 KB ok
22 Correct 30 ms 121688 KB ok
23 Partially correct 29 ms 121876 KB partial
24 Partially correct 30 ms 121688 KB partial
25 Correct 36 ms 121624 KB ok
26 Correct 27 ms 121692 KB ok
27 Correct 26 ms 121552 KB ok
28 Correct 30 ms 121596 KB ok
29 Correct 30 ms 121692 KB ok
30 Correct 28 ms 121648 KB ok
31 Partially correct 32 ms 121692 KB partial
32 Partially correct 29 ms 121624 KB partial
33 Partially correct 30 ms 121544 KB partial
34 Partially correct 32 ms 121664 KB partial
35 Correct 35 ms 123680 KB ok
36 Correct 35 ms 123732 KB ok
37 Correct 33 ms 123732 KB ok
38 Correct 27 ms 123680 KB ok
39 Correct 28 ms 123708 KB ok
40 Correct 27 ms 123648 KB ok
41 Correct 26 ms 123728 KB ok
42 Partially correct 26 ms 123612 KB partial
43 Partially correct 27 ms 123740 KB partial
44 Partially correct 27 ms 123544 KB partial
45 Correct 27 ms 123600 KB ok
46 Partially correct 27 ms 123684 KB partial
47 Partially correct 75 ms 145624 KB partial
48 Partially correct 74 ms 145232 KB partial
49 Partially correct 72 ms 146336 KB partial
50 Partially correct 69 ms 147116 KB partial
51 Partially correct 67 ms 145856 KB partial
52 Partially correct 97 ms 150456 KB partial
53 Incorrect 82 ms 145976 KB wrong
54 Halted 0 ms 0 KB -