oj.uz

Submission #929991

# Submission time Handle Problem Language Result Execution time Memory
929991 2024-02-18T08:58:14 Z abcvuitunggio Soccer Stadium (IOI23_soccer) C++17
18 / 100
 507 ms 242004 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],a[mxn][mxn],b[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);
    }
    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]||r[i][j]<r[st.top()][j])){
                d[st.top()][j]=i-1;
                st.pop();
            }
            if (!st.empty()){
                if (r[i][j]-l[i][j]==r[st.top()][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]||r[i][j]<r[st.top()][j])){
                u[st.top()][j]=i+1;
                st.pop();
            }
            if (!st.empty()){
                if (r[i][j]-l[i][j]==r[st.top()][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));
    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 56 ms 155220 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 151132 KB ok
2 Correct 28 ms 151128 KB ok
3 Correct 30 ms 155212 KB ok
4 Correct 30 ms 155224 KB ok
5 Correct 31 ms 151132 KB ok
6 Correct 30 ms 153176 KB ok
7 Correct 30 ms 155472 KB ok
8 Correct 63 ms 173652 KB ok
9 Correct 507 ms 242004 KB ok

Subtask #2
2.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 151132 KB ok
2 Correct 28 ms 151128 KB ok
3 Correct 32 ms 151128 KB ok
4 Correct 35 ms 153196 KB ok
5 Correct 34 ms 153168 KB ok
6 Correct 30 ms 153180 KB ok
7 Partially correct 33 ms 153168 KB partial
8 Correct 31 ms 153180 KB ok
9 Correct 33 ms 151124 KB ok
10 Correct 30 ms 153176 KB ok
11 Correct 31 ms 153180 KB ok
12 Correct 29 ms 153208 KB ok
13 Correct 30 ms 153036 KB ok

Subtask #3
5.5 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 155220 KB ok
2 Correct 29 ms 151132 KB ok
3 Correct 28 ms 151128 KB ok
4 Correct 32 ms 151128 KB ok
5 Correct 35 ms 153196 KB ok
6 Correct 34 ms 153168 KB ok
7 Correct 30 ms 153180 KB ok
8 Partially correct 33 ms 153168 KB partial
9 Correct 31 ms 153180 KB ok
10 Correct 33 ms 151124 KB ok
11 Correct 30 ms 153176 KB ok
12 Correct 31 ms 153180 KB ok
13 Correct 29 ms 153208 KB ok
14 Correct 30 ms 153036 KB ok
15 Correct 32 ms 155228 KB ok
16 Partially correct 31 ms 155228 KB partial
17 Partially correct 33 ms 155220 KB partial
18 Correct 30 ms 155252 KB ok
19 Correct 32 ms 155224 KB ok
20 Correct 34 ms 155216 KB ok
21 Correct 34 ms 155184 KB ok
22 Correct 32 ms 155232 KB ok
23 Correct 33 ms 155228 KB ok
24 Partially correct 31 ms 155224 KB partial
25 Partially correct 31 ms 155224 KB partial
26 Partially correct 29 ms 155204 KB partial

Subtask #4
4.5 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 155220 KB ok
2 Correct 29 ms 151132 KB ok
3 Correct 28 ms 151128 KB ok
4 Correct 30 ms 155212 KB ok
5 Correct 30 ms 155224 KB ok
6 Correct 32 ms 151128 KB ok
7 Correct 35 ms 153196 KB ok
8 Correct 34 ms 153168 KB ok
9 Correct 30 ms 153180 KB ok
10 Partially correct 33 ms 153168 KB partial
11 Correct 31 ms 153180 KB ok
12 Correct 33 ms 151124 KB ok
13 Correct 30 ms 153176 KB ok
14 Correct 31 ms 153180 KB ok
15 Correct 29 ms 153208 KB ok
16 Correct 30 ms 153036 KB ok
17 Correct 32 ms 155228 KB ok
18 Partially correct 31 ms 155228 KB partial
19 Partially correct 33 ms 155220 KB partial
20 Correct 30 ms 155252 KB ok
21 Correct 32 ms 155224 KB ok
22 Correct 34 ms 155216 KB ok
23 Correct 34 ms 155184 KB ok
24 Correct 32 ms 155232 KB ok
25 Correct 33 ms 155228 KB ok
26 Partially correct 31 ms 155224 KB partial
27 Partially correct 31 ms 155224 KB partial
28 Partially correct 29 ms 155204 KB partial
29 Partially correct 33 ms 155224 KB partial
30 Partially correct 33 ms 155216 KB partial
31 Correct 34 ms 155228 KB ok
32 Correct 32 ms 155184 KB ok
33 Correct 32 ms 155092 KB ok
34 Correct 31 ms 155184 KB ok
35 Correct 32 ms 155260 KB ok
36 Correct 32 ms 155216 KB ok
37 Partially correct 30 ms 155228 KB partial
38 Partially correct 32 ms 155268 KB partial
39 Partially correct 31 ms 155228 KB partial
40 Correct 31 ms 155216 KB ok
41 Partially correct 31 ms 155220 KB partial

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 155220 KB ok
2 Correct 29 ms 151132 KB ok
3 Correct 28 ms 151128 KB ok
4 Correct 30 ms 155212 KB ok
5 Correct 30 ms 155224 KB ok
6 Correct 32 ms 151128 KB ok
7 Correct 35 ms 153196 KB ok
8 Correct 34 ms 153168 KB ok
9 Correct 30 ms 153180 KB ok
10 Partially correct 33 ms 153168 KB partial
11 Correct 31 ms 153180 KB ok
12 Correct 33 ms 151124 KB ok
13 Correct 30 ms 153176 KB ok
14 Correct 31 ms 153180 KB ok
15 Correct 29 ms 153208 KB ok
16 Correct 30 ms 153036 KB ok
17 Correct 32 ms 155228 KB ok
18 Partially correct 31 ms 155228 KB partial
19 Partially correct 33 ms 155220 KB partial
20 Correct 30 ms 155252 KB ok
21 Correct 32 ms 155224 KB ok
22 Correct 34 ms 155216 KB ok
23 Correct 34 ms 155184 KB ok
24 Correct 32 ms 155232 KB ok
25 Correct 33 ms 155228 KB ok
26 Partially correct 31 ms 155224 KB partial
27 Partially correct 31 ms 155224 KB partial
28 Partially correct 29 ms 155204 KB partial
29 Partially correct 33 ms 155224 KB partial
30 Partially correct 33 ms 155216 KB partial
31 Correct 34 ms 155228 KB ok
32 Correct 32 ms 155184 KB ok
33 Correct 32 ms 155092 KB ok
34 Correct 31 ms 155184 KB ok
35 Correct 32 ms 155260 KB ok
36 Correct 32 ms 155216 KB ok
37 Partially correct 30 ms 155228 KB partial
38 Partially correct 32 ms 155268 KB partial
39 Partially correct 31 ms 155228 KB partial
40 Correct 31 ms 155216 KB ok
41 Partially correct 31 ms 155220 KB partial
42 Partially correct 78 ms 176856 KB partial
43 Partially correct 83 ms 176084 KB partial
44 Partially correct 77 ms 177388 KB partial
45 Partially correct 72 ms 177912 KB partial
46 Partially correct 75 ms 176976 KB partial
47 Partially correct 55 ms 173652 KB partial
48 Incorrect 68 ms 176340 KB wrong
49 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 155220 KB ok
2 Correct 29 ms 151132 KB ok
3 Correct 28 ms 151128 KB ok
4 Correct 30 ms 155212 KB ok
5 Correct 30 ms 155224 KB ok
6 Correct 31 ms 151132 KB ok
7 Correct 30 ms 153176 KB ok
8 Correct 30 ms 155472 KB ok
9 Correct 63 ms 173652 KB ok
10 Correct 507 ms 242004 KB ok
11 Correct 32 ms 151128 KB ok
12 Correct 35 ms 153196 KB ok
13 Correct 34 ms 153168 KB ok
14 Correct 30 ms 153180 KB ok
15 Partially correct 33 ms 153168 KB partial
16 Correct 31 ms 153180 KB ok
17 Correct 33 ms 151124 KB ok
18 Correct 30 ms 153176 KB ok
19 Correct 31 ms 153180 KB ok
20 Correct 29 ms 153208 KB ok
21 Correct 30 ms 153036 KB ok
22 Correct 32 ms 155228 KB ok
23 Partially correct 31 ms 155228 KB partial
24 Partially correct 33 ms 155220 KB partial
25 Correct 30 ms 155252 KB ok
26 Correct 32 ms 155224 KB ok
27 Correct 34 ms 155216 KB ok
28 Correct 34 ms 155184 KB ok
29 Correct 32 ms 155232 KB ok
30 Correct 33 ms 155228 KB ok
31 Partially correct 31 ms 155224 KB partial
32 Partially correct 31 ms 155224 KB partial
33 Partially correct 29 ms 155204 KB partial
34 Partially correct 33 ms 155224 KB partial
35 Partially correct 33 ms 155216 KB partial
36 Correct 34 ms 155228 KB ok
37 Correct 32 ms 155184 KB ok
38 Correct 32 ms 155092 KB ok
39 Correct 31 ms 155184 KB ok
40 Correct 32 ms 155260 KB ok
41 Correct 32 ms 155216 KB ok
42 Partially correct 30 ms 155228 KB partial
43 Partially correct 32 ms 155268 KB partial
44 Partially correct 31 ms 155228 KB partial
45 Correct 31 ms 155216 KB ok
46 Partially correct 31 ms 155220 KB partial
47 Partially correct 78 ms 176856 KB partial
48 Partially correct 83 ms 176084 KB partial
49 Partially correct 77 ms 177388 KB partial
50 Partially correct 72 ms 177912 KB partial
51 Partially correct 75 ms 176976 KB partial
52 Partially correct 55 ms 173652 KB partial
53 Incorrect 68 ms 176340 KB wrong
54 Halted 0 ms 0 KB -