oj.uz

Submission #930025

# Submission time Handle Problem Language Result Execution time Memory
930025 2024-02-18T09:02:30 Z abcvuitunggio Soccer Stadium (IOI23_soccer) C++17
18 / 100
 694 ms 268200 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn=2006;
int n,res,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 solve(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);
            u[i][j]=ch[i][j]=0;
            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));
    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;
}
int biggest_stadium(int N, vector <vector <int>> F){
    n=N;
    res=solve(F);
    for (int i=0;i<n;i++)
        for (int j=i;j<n;j++)
            swap(F[i][j],F[j][i]);
    return max(res,solve(F));
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 155216 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 155240 KB ok
2 Correct 36 ms 155228 KB ok
3 Correct 38 ms 155128 KB ok
4 Correct 38 ms 155220 KB ok
5 Correct 32 ms 153176 KB ok
6 Correct 33 ms 155228 KB ok
7 Correct 35 ms 157276 KB ok
8 Correct 63 ms 174656 KB ok
9 Correct 694 ms 268200 KB ok

Subtask #2
2.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 155240 KB ok
2 Correct 36 ms 155228 KB ok
3 Correct 33 ms 155224 KB ok
4 Correct 34 ms 155256 KB ok
5 Correct 37 ms 155508 KB ok
6 Correct 33 ms 155244 KB ok
7 Partially correct 34 ms 155216 KB partial
8 Correct 34 ms 155220 KB ok
9 Correct 36 ms 155212 KB ok
10 Correct 35 ms 155080 KB ok
11 Correct 34 ms 155120 KB ok
12 Correct 36 ms 155476 KB ok
13 Correct 33 ms 155216 KB ok

Subtask #3
5.5 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 155216 KB ok
2 Correct 36 ms 155240 KB ok
3 Correct 36 ms 155228 KB ok
4 Correct 33 ms 155224 KB ok
5 Correct 34 ms 155256 KB ok
6 Correct 37 ms 155508 KB ok
7 Correct 33 ms 155244 KB ok
8 Partially correct 34 ms 155216 KB partial
9 Correct 34 ms 155220 KB ok
10 Correct 36 ms 155212 KB ok
11 Correct 35 ms 155080 KB ok
12 Correct 34 ms 155120 KB ok
13 Correct 36 ms 155476 KB ok
14 Correct 33 ms 155216 KB ok
15 Correct 38 ms 155228 KB ok
16 Correct 34 ms 155004 KB ok
17 Partially correct 35 ms 155224 KB partial
18 Correct 37 ms 155216 KB ok
19 Correct 34 ms 155136 KB ok
20 Correct 35 ms 155264 KB ok
21 Correct 33 ms 155220 KB ok
22 Partially correct 35 ms 155228 KB partial
23 Correct 33 ms 155228 KB ok
24 Correct 35 ms 155228 KB ok
25 Correct 37 ms 155188 KB ok
26 Partially correct 37 ms 155252 KB partial

Subtask #4
4.5 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 155216 KB ok
2 Correct 36 ms 155240 KB ok
3 Correct 36 ms 155228 KB ok
4 Correct 38 ms 155128 KB ok
5 Correct 38 ms 155220 KB ok
6 Correct 33 ms 155224 KB ok
7 Correct 34 ms 155256 KB ok
8 Correct 37 ms 155508 KB ok
9 Correct 33 ms 155244 KB ok
10 Partially correct 34 ms 155216 KB partial
11 Correct 34 ms 155220 KB ok
12 Correct 36 ms 155212 KB ok
13 Correct 35 ms 155080 KB ok
14 Correct 34 ms 155120 KB ok
15 Correct 36 ms 155476 KB ok
16 Correct 33 ms 155216 KB ok
17 Correct 38 ms 155228 KB ok
18 Correct 34 ms 155004 KB ok
19 Partially correct 35 ms 155224 KB partial
20 Correct 37 ms 155216 KB ok
21 Correct 34 ms 155136 KB ok
22 Correct 35 ms 155264 KB ok
23 Correct 33 ms 155220 KB ok
24 Partially correct 35 ms 155228 KB partial
25 Correct 33 ms 155228 KB ok
26 Correct 35 ms 155228 KB ok
27 Correct 37 ms 155188 KB ok
28 Partially correct 37 ms 155252 KB partial
29 Partially correct 35 ms 155256 KB partial
30 Partially correct 33 ms 155216 KB partial
31 Correct 33 ms 155228 KB ok
32 Partially correct 34 ms 155228 KB partial
33 Correct 36 ms 155232 KB ok
34 Correct 34 ms 155224 KB ok
35 Correct 33 ms 155104 KB ok
36 Correct 33 ms 155224 KB ok
37 Correct 35 ms 155216 KB ok
38 Correct 33 ms 155228 KB ok
39 Partially correct 34 ms 155284 KB partial
40 Correct 34 ms 155220 KB ok
41 Partially correct 33 ms 155224 KB partial

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 155216 KB ok
2 Correct 36 ms 155240 KB ok
3 Correct 36 ms 155228 KB ok
4 Correct 38 ms 155128 KB ok
5 Correct 38 ms 155220 KB ok
6 Correct 33 ms 155224 KB ok
7 Correct 34 ms 155256 KB ok
8 Correct 37 ms 155508 KB ok
9 Correct 33 ms 155244 KB ok
10 Partially correct 34 ms 155216 KB partial
11 Correct 34 ms 155220 KB ok
12 Correct 36 ms 155212 KB ok
13 Correct 35 ms 155080 KB ok
14 Correct 34 ms 155120 KB ok
15 Correct 36 ms 155476 KB ok
16 Correct 33 ms 155216 KB ok
17 Correct 38 ms 155228 KB ok
18 Correct 34 ms 155004 KB ok
19 Partially correct 35 ms 155224 KB partial
20 Correct 37 ms 155216 KB ok
21 Correct 34 ms 155136 KB ok
22 Correct 35 ms 155264 KB ok
23 Correct 33 ms 155220 KB ok
24 Partially correct 35 ms 155228 KB partial
25 Correct 33 ms 155228 KB ok
26 Correct 35 ms 155228 KB ok
27 Correct 37 ms 155188 KB ok
28 Partially correct 37 ms 155252 KB partial
29 Partially correct 35 ms 155256 KB partial
30 Partially correct 33 ms 155216 KB partial
31 Correct 33 ms 155228 KB ok
32 Partially correct 34 ms 155228 KB partial
33 Correct 36 ms 155232 KB ok
34 Correct 34 ms 155224 KB ok
35 Correct 33 ms 155104 KB ok
36 Correct 33 ms 155224 KB ok
37 Correct 35 ms 155216 KB ok
38 Correct 33 ms 155228 KB ok
39 Partially correct 34 ms 155284 KB partial
40 Correct 34 ms 155220 KB ok
41 Partially correct 33 ms 155224 KB partial
42 Partially correct 102 ms 179752 KB partial
43 Partially correct 115 ms 178768 KB partial
44 Partially correct 100 ms 180976 KB partial
45 Partially correct 100 ms 181328 KB partial
46 Partially correct 99 ms 180224 KB partial
47 Partially correct 73 ms 175088 KB partial
48 Incorrect 83 ms 178500 KB wrong
49 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 155216 KB ok
2 Correct 36 ms 155240 KB ok
3 Correct 36 ms 155228 KB ok
4 Correct 38 ms 155128 KB ok
5 Correct 38 ms 155220 KB ok
6 Correct 32 ms 153176 KB ok
7 Correct 33 ms 155228 KB ok
8 Correct 35 ms 157276 KB ok
9 Correct 63 ms 174656 KB ok
10 Correct 694 ms 268200 KB ok
11 Correct 33 ms 155224 KB ok
12 Correct 34 ms 155256 KB ok
13 Correct 37 ms 155508 KB ok
14 Correct 33 ms 155244 KB ok
15 Partially correct 34 ms 155216 KB partial
16 Correct 34 ms 155220 KB ok
17 Correct 36 ms 155212 KB ok
18 Correct 35 ms 155080 KB ok
19 Correct 34 ms 155120 KB ok
20 Correct 36 ms 155476 KB ok
21 Correct 33 ms 155216 KB ok
22 Correct 38 ms 155228 KB ok
23 Correct 34 ms 155004 KB ok
24 Partially correct 35 ms 155224 KB partial
25 Correct 37 ms 155216 KB ok
26 Correct 34 ms 155136 KB ok
27 Correct 35 ms 155264 KB ok
28 Correct 33 ms 155220 KB ok
29 Partially correct 35 ms 155228 KB partial
30 Correct 33 ms 155228 KB ok
31 Correct 35 ms 155228 KB ok
32 Correct 37 ms 155188 KB ok
33 Partially correct 37 ms 155252 KB partial
34 Partially correct 35 ms 155256 KB partial
35 Partially correct 33 ms 155216 KB partial
36 Correct 33 ms 155228 KB ok
37 Partially correct 34 ms 155228 KB partial
38 Correct 36 ms 155232 KB ok
39 Correct 34 ms 155224 KB ok
40 Correct 33 ms 155104 KB ok
41 Correct 33 ms 155224 KB ok
42 Correct 35 ms 155216 KB ok
43 Correct 33 ms 155228 KB ok
44 Partially correct 34 ms 155284 KB partial
45 Correct 34 ms 155220 KB ok
46 Partially correct 33 ms 155224 KB partial
47 Partially correct 102 ms 179752 KB partial
48 Partially correct 115 ms 178768 KB partial
49 Partially correct 100 ms 180976 KB partial
50 Partially correct 100 ms 181328 KB partial
51 Partially correct 99 ms 180224 KB partial
52 Partially correct 73 ms 175088 KB partial
53 Incorrect 83 ms 178500 KB wrong
54 Halted 0 ms 0 KB -