oj.uz

Submission #1010504

# Submission time Handle Problem Language Result Execution time Memory
1010504 2024-06-29T07:26:15 Z ttamx Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 267364 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];
vector<pair<int,int>> rect[N];
int ans;
map<tuple<int,int,int,int>,int> mem;
map<tuple<int,int,int,int>,bool> vis;

int& get(int i,int j){
    int l=pre[i][j][0]+1,r=j,t=top[i][j],b=bot[i][j];
    return mem[{l,r,t,b}];
}

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(vis[{l,r,t,b}])continue;
        vis[{l,r,t,b}]=true;
        int h=b-t+1;
        int res=w*h+get(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;
                get(p,nr)=max(get(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;
                get(p,nr)=max(get(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:27:13: warning: unused variable 't' [-Wunused-variable]
   27 |         int t=0,b=n+1;
      |             ^
soccer.cpp:27:17: warning: unused variable 'b' [-Wunused-variable]
   27 |         int t=0,b=n+1;
      |                 ^

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.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 604 KB ok
4 Correct 0 ms 604 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 2 ms 2396 KB ok
8 Correct 26 ms 17488 KB ok
9 Correct 427 ms 142992 KB ok

Subtask #2
8.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 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 344 KB ok
13 Correct 0 ms 348 KB ok

Subtask #3
22.0 / 22.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 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 344 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 604 KB ok
16 Correct 0 ms 604 KB ok
17 Correct 0 ms 604 KB ok
18 Correct 0 ms 604 KB ok
19 Correct 0 ms 580 KB ok
20 Correct 0 ms 604 KB ok
21 Correct 0 ms 604 KB ok
22 Correct 0 ms 604 KB ok
23 Correct 1 ms 600 KB ok
24 Correct 1 ms 604 KB ok
25 Correct 0 ms 604 KB ok
26 Correct 1 ms 604 KB ok

Subtask #4
18.0 / 18.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 604 KB ok
5 Correct 0 ms 604 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 344 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 604 KB ok
18 Correct 0 ms 604 KB ok
19 Correct 0 ms 604 KB ok
20 Correct 0 ms 604 KB ok
21 Correct 0 ms 580 KB ok
22 Correct 0 ms 604 KB ok
23 Correct 0 ms 604 KB ok
24 Correct 0 ms 604 KB ok
25 Correct 1 ms 600 KB ok
26 Correct 1 ms 604 KB ok
27 Correct 0 ms 604 KB ok
28 Correct 1 ms 604 KB ok
29 Correct 1 ms 604 KB ok
30 Correct 1 ms 1112 KB ok
31 Correct 1 ms 860 KB ok
32 Correct 1 ms 860 KB ok
33 Correct 0 ms 860 KB ok
34 Correct 0 ms 860 KB ok
35 Correct 1 ms 856 KB ok
36 Correct 0 ms 860 KB ok
37 Correct 0 ms 860 KB ok
38 Correct 1 ms 860 KB ok
39 Correct 0 ms 860 KB ok
40 Correct 1 ms 860 KB ok
41 Correct 1 ms 860 KB ok

Subtask #5
16.0 / 16.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 604 KB ok
5 Correct 0 ms 604 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 344 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 604 KB ok
18 Correct 0 ms 604 KB ok
19 Correct 0 ms 604 KB ok
20 Correct 0 ms 604 KB ok
21 Correct 0 ms 580 KB ok
22 Correct 0 ms 604 KB ok
23 Correct 0 ms 604 KB ok
24 Correct 0 ms 604 KB ok
25 Correct 1 ms 600 KB ok
26 Correct 1 ms 604 KB ok
27 Correct 0 ms 604 KB ok
28 Correct 1 ms 604 KB ok
29 Correct 1 ms 604 KB ok
30 Correct 1 ms 1112 KB ok
31 Correct 1 ms 860 KB ok
32 Correct 1 ms 860 KB ok
33 Correct 0 ms 860 KB ok
34 Correct 0 ms 860 KB ok
35 Correct 1 ms 856 KB ok
36 Correct 0 ms 860 KB ok
37 Correct 0 ms 860 KB ok
38 Correct 1 ms 860 KB ok
39 Correct 0 ms 860 KB ok
40 Correct 1 ms 860 KB ok
41 Correct 1 ms 860 KB ok
42 Correct 537 ms 41484 KB ok
43 Correct 386 ms 37312 KB ok
44 Correct 641 ms 44920 KB ok
45 Correct 518 ms 41916 KB ok
46 Correct 605 ms 44368 KB ok
47 Correct 34 ms 18508 KB ok
48 Correct 69 ms 21920 KB ok
49 Correct 66 ms 22352 KB ok
50 Correct 1210 ms 32552 KB ok
51 Correct 166 ms 31948 KB ok
52 Correct 32 ms 17500 KB ok
53 Correct 22 ms 16476 KB ok
54 Correct 38 ms 16468 KB ok
55 Correct 56 ms 19532 KB ok
56 Correct 24 ms 16988 KB ok
57 Correct 151 ms 33620 KB ok
58 Correct 166 ms 34636 KB ok
59 Correct 213 ms 36176 KB ok

Subtask #6
0.0 / 30.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 604 KB ok
5 Correct 0 ms 604 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 2 ms 2396 KB ok
9 Correct 26 ms 17488 KB ok
10 Correct 427 ms 142992 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 344 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 604 KB ok
23 Correct 0 ms 604 KB ok
24 Correct 0 ms 604 KB ok
25 Correct 0 ms 604 KB ok
26 Correct 0 ms 580 KB ok
27 Correct 0 ms 604 KB ok
28 Correct 0 ms 604 KB ok
29 Correct 0 ms 604 KB ok
30 Correct 1 ms 600 KB ok
31 Correct 1 ms 604 KB ok
32 Correct 0 ms 604 KB ok
33 Correct 1 ms 604 KB ok
34 Correct 1 ms 604 KB ok
35 Correct 1 ms 1112 KB ok
36 Correct 1 ms 860 KB ok
37 Correct 1 ms 860 KB ok
38 Correct 0 ms 860 KB ok
39 Correct 0 ms 860 KB ok
40 Correct 1 ms 856 KB ok
41 Correct 0 ms 860 KB ok
42 Correct 0 ms 860 KB ok
43 Correct 1 ms 860 KB ok
44 Correct 0 ms 860 KB ok
45 Correct 1 ms 860 KB ok
46 Correct 1 ms 860 KB ok
47 Correct 537 ms 41484 KB ok
48 Correct 386 ms 37312 KB ok
49 Correct 641 ms 44920 KB ok
50 Correct 518 ms 41916 KB ok
51 Correct 605 ms 44368 KB ok
52 Correct 34 ms 18508 KB ok
53 Correct 69 ms 21920 KB ok
54 Correct 66 ms 22352 KB ok
55 Correct 1210 ms 32552 KB ok
56 Correct 166 ms 31948 KB ok
57 Correct 32 ms 17500 KB ok
58 Correct 22 ms 16476 KB ok
59 Correct 38 ms 16468 KB ok
60 Correct 56 ms 19532 KB ok
61 Correct 24 ms 16988 KB ok
62 Correct 151 ms 33620 KB ok
63 Correct 166 ms 34636 KB ok
64 Correct 213 ms 36176 KB ok
65 Execution timed out 4572 ms 267364 KB Time limit exceeded
66 Halted 0 ms 0 KB -