oj.uz

Submission #1010499

# Submission time Handle Problem Language Result Execution time Memory
1010499 2024-06-29T07:23:32 Z ttamx Soccer Stadium (IOI23_soccer) C++17
0 / 100
 1 ms 604 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;
map<tuple<int,int,int,int>,int> mem;

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]?min(i,i>1?top[i-1][j]:n+1):n+1;
    for(int i=n;i>=1;i--)for(int j=1;j<=n;j++)bot[i][j]=a[i][j]?max(i,bot[i+1][j]):0;
    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(mem.count({l,r,t,b})){
            dp[i][j]=mem[{l,r,t,b}];
            continue;
        }
        mem[{l,r,t,b}]=dp[i][j];
        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 0 ms 604 KB ok

Subtask #1
0.0 / 6.0

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

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Partially correct 0 ms 348 KB partial
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 344 KB ok
8 Incorrect 0 ms 348 KB wrong
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Partially correct 0 ms 348 KB partial
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 344 KB ok
9 Incorrect 0 ms 348 KB wrong
10 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

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

Subtask #5
0.0 / 16.0

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

Subtask #6
0.0 / 30.0

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