oj.uz

Submission #1010530

# Submission time Handle Problem Language Result Execution time Memory
1010530 2024-06-29T07:43:26 Z ttamx Soccer Stadium (IOI23_soccer) C++17
2 / 100
 1 ms 2904 KB 
#include "soccer.h"
#include <bits/stdc++.h>

using namespace std;

const int N=2005;

int n;
int a[N][N];
int top[N][N],bot[N][N],pre[N][N][2],dp[N][N];
vector<pair<int,int>> rect[N];
int ans;

int biggest_stadium(int _n,vector<vector<int>> _a){
    n=_n;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=_a[i-1][j-1]^1;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)top[i][j]=a[i][j]?a[i-1][j]?top[i-1][j]:i:top[i-1][j];
    for(int i=1;i<=n;i++)bot[n+1][i]=n+1;
    for(int i=n;i>=1;i--)for(int j=1;j<=n;j++)bot[i][j]=a[i][j]?a[i+1][j]?bot[i+1][j]:i:bot[i+1][j];
    for(int i=1;i<=n;i++){
        int t=0,b=n+1;
        for(int j=1;j<=n;j++){
            for(int x=0;x<2;x++)pre[i][j][x]=a[i][j]==x?j:pre[i][j-1][x];
            if(a[i][j]){
                if(a[i][j-1]){
                    top[i][j]=max(top[i][j],top[i][j-1]);
                    bot[i][j]=min(bot[i][j],bot[i][j-1]);
                }
                rect[j-pre[i][j][0]].emplace_back(i,j);
            }
        }
    }
    for(int w=n;w>=1;w--)for(auto [i,j]:rect[w]){
        int l=pre[i][j][0]+1,r=j,t=top[i][j],b=bot[i][j];
        if(a[i][j+1]&&top[i][j+1]<=t&&bot[i][j+1]>=b)continue;
        int lw=bot[i][l-1];
        if(lw>0&&lw<=b){
            dp[lw][j]=max(dp[lw][j],dp[i][j]);
            continue;
        }
        int h=b-t+1;
        int res=w*h+dp[i][j];
        ans=max(ans,res);
        if(t>1){
            for(int nr=pre[t-1][r][1],nl;nr>=l;nr=pre[t-1][nl][1]){
                nl=max(l-1,pre[t-1][nr][0]);
                int p=nl>=l?t-1:i;
                dp[p][nr]=max(dp[p][nr],res-(nr-nl)*h);
            }
        }
        if(b<n){
            for(int nr=pre[b+1][r][1],nl;nr>=l;nr=pre[b+1][nl][1]){
                nl=max(l-1,pre[b+1][nr][0]);
                int p=nl>=l?b+1:i;
                dp[p][nr]=max(dp[p][nr],res-(nr-nl)*h);
            }
        }
    }
    return ans;
}

Compilation message

soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:21:13: warning: unused variable 't' [-Wunused-variable]
   21 |         int t=0,b=n+1;
      |             ^
soccer.cpp:21:17: warning: unused variable 'b' [-Wunused-variable]
   21 |         int t=0,b=n+1;
      |                 ^

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Incorrect 1 ms 604 KB wrong
4 Halted 0 ms 0 KB -

Subtask #2
2.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 2544 KB ok
5 Correct 0 ms 348 KB ok
6 Partially correct 0 ms 600 KB partial
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 1 ms 2396 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 344 KB ok
12 Correct 1 ms 348 KB ok
13 Correct 0 ms 348 KB ok

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 2544 KB ok
6 Correct 0 ms 348 KB ok
7 Partially correct 0 ms 600 KB partial
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 1 ms 2396 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 344 KB ok
13 Correct 1 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Partially correct 1 ms 2904 KB partial
16 Partially correct 0 ms 604 KB partial
17 Correct 1 ms 604 KB ok
18 Correct 0 ms 604 KB ok
19 Partially correct 1 ms 604 KB partial
20 Correct 0 ms 604 KB ok
21 Incorrect 0 ms 604 KB wrong
22 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Incorrect 1 ms 604 KB wrong
5 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Incorrect 1 ms 604 KB wrong
5 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Incorrect 1 ms 604 KB wrong
5 Halted 0 ms 0 KB -