oj.uz

Submission #928182

# Submission time Handle Problem Language Result Execution time Memory
928182 2024-02-16T03:35:30 Z abcvuitunggio Soccer Stadium (IOI23_soccer) C++17
0 / 100
 111 ms 505912 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn=502;
int n,ans,dp[mxn][mxn][mxn],s[2001][2001],l[mxn][mxn][mxn],r[mxn][mxn][mxn];
int sum(int l, int r, int i){
    return s[r][i]-s[l][i];
}
int f(int i, int j, int k){
    if (i==j)
        return 0;
    if (dp[i][j][k]!=-1)
        return dp[i][j][k];
    return dp[i][j][k]=max(f(i+1,j,k)+(l[i][j][k]-l[i+1][j][k]+r[i+1][j][k]-r[i][j][k])*(j-i-1),f(i,j-1,k)+(l[i][j][k]-l[i][j-1][k]+r[i][j-1][k]-r[i][j][k])*(j-i-1));
}
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++)
            s[i+1][j]=s[i][j]+F[i][j];
    for (int k=0;k<=n;k++)
        for (int i=0;i<n;i++){
            int x=k,y=k;
            for (int j=n;j>i;j--){
                while (x&&!sum(i,j,x-1))
                    x--;
                l[i][j][k]=x;
                while (y<k&&!sum(i,j,y))
                    y++;
                r[i][j][k]=y;
            }
        }
    memset(dp,-1,sizeof(dp));
    for (int i=0;i<=n;i++)
        ans=max(ans,f(0,n,i)+(r[0][n][i]-l[0][n][i])*n);
    return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 505912 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 111 ms 501788 KB wrong
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 111 ms 501788 KB wrong
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 505912 KB ok
2 Incorrect 111 ms 501788 KB wrong
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 505912 KB ok
2 Incorrect 111 ms 501788 KB wrong
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 505912 KB ok
2 Incorrect 111 ms 501788 KB wrong
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 505912 KB ok
2 Incorrect 111 ms 501788 KB wrong
3 Halted 0 ms 0 KB -