oj.uz

Submission #846989

# Submission time Handle Problem Language Result Execution time Memory
846989 2023-09-08T21:08:37 Z firewater Soccer Stadium (IOI23_soccer) C++17
100 / 100
 1201 ms 147352 KB 
#include "soccer.h"
#include<bits/stdc++.h>
#define fs first
#define sn second
#define MX 2020
using namespace std;
int n,ans,tot,a[MX][MX],sum[MX][MX];
map<pair<int,pair<int,int> >,int>f;
pair<int,int>sav;
int get(int x1,int x2,int y1,int y2)
{
    if(x1>x2||y1>y2)return 0;
    return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
}
pair<int,int>find(int x,int L,int R)
{
    int ansl,ansr,l,r;
    l=1;r=x+1;
    while(l<r){
        int mid=l+r>>1;
        if(!get(mid,x,L,R))r=mid;
        else l=mid+1;
    }
    ansl=l;
    l=x-1;r=n;
    while(l<r){
        int mid=l+r+1>>1;
        if(!get(x,mid,L,R))l=mid;
        else r=mid-1;
    }
    ansr=l;
    return {ansl,ansr};
}
int solve(int x,int L,int R)
{
    if(f.count({x,{L,R}}))return f[{x,{L,R}}];
    pair<int,int>sav=find(x,L,R),k;
    int num=(R-L+1)*max(0,sav.sn-sav.fs+1),l,r;

    if(sav.fs==1&&sav.sn==n)return num;
    if(x>sav.fs)return solve(sav.fs,L,R);

    for(int li=L,ri=L;ri<=R;++li,ri=max(li,ri)){
        if((sav.fs==1||get(sav.fs-1,x,li,ri))&&(sav.sn==n||get(x,sav.sn+1,li,ri)))continue;
        l=ri;
        r=R;
        while(l<r){
            int mid=l+r+1>>1;
            if((sav.fs>1&&!get(sav.fs-1,x,li,mid))||(sav.sn<n&&!get(x,sav.sn+1,li,mid)))l=mid;
            else r=mid-1;
        }
        ri=l;
        num=max(num,solve(x,li,ri)+(R-ri+li-L)*max(0,sav.sn-sav.fs+1));
        ri++;
    }
    return f[{x,{L,R}}]=num;
}
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    n=N;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j){
            a[i][j]=F[i-1][j-1];
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
        }
    for(int i=1;i<=n;++i)
        ans=max(ans,solve(i,1,n));
    return ans;
}

Compilation message

soccer.cpp: In function 'std::pair<int, int> find(int, int, int)':
soccer.cpp:20:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |         int mid=l+r>>1;
      |                 ~^~
soccer.cpp:27:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |         int mid=l+r+1>>1;
      |                 ~~~^~
soccer.cpp: In function 'int solve(int, int, int)':
soccer.cpp:48:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |             int mid=l+r+1>>1;
      |                     ~~~^~

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB ok
2 Correct 0 ms 2396 KB ok
3 Correct 0 ms 2396 KB ok
4 Correct 1 ms 2396 KB ok
5 Correct 0 ms 2396 KB ok
6 Correct 1 ms 2392 KB ok
7 Correct 2 ms 5220 KB ok
8 Correct 21 ms 12172 KB ok
9 Correct 260 ms 63524 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB ok
2 Correct 0 ms 2396 KB ok
3 Correct 1 ms 2392 KB ok
4 Correct 0 ms 2396 KB ok
5 Correct 1 ms 2396 KB ok
6 Correct 1 ms 2396 KB ok
7 Correct 1 ms 2396 KB ok
8 Correct 1 ms 2396 KB ok
9 Correct 1 ms 2396 KB ok
10 Correct 0 ms 2444 KB ok
11 Correct 1 ms 2396 KB ok
12 Correct 1 ms 2392 KB ok
13 Correct 0 ms 2396 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB ok
2 Correct 1 ms 2396 KB ok
3 Correct 0 ms 2396 KB ok
4 Correct 1 ms 2392 KB ok
5 Correct 0 ms 2396 KB ok
6 Correct 1 ms 2396 KB ok
7 Correct 1 ms 2396 KB ok
8 Correct 1 ms 2396 KB ok
9 Correct 1 ms 2396 KB ok
10 Correct 1 ms 2396 KB ok
11 Correct 0 ms 2444 KB ok
12 Correct 1 ms 2396 KB ok
13 Correct 1 ms 2392 KB ok
14 Correct 0 ms 2396 KB ok
15 Correct 1 ms 2392 KB ok
16 Correct 1 ms 2396 KB ok
17 Correct 1 ms 2396 KB ok
18 Correct 1 ms 2396 KB ok
19 Correct 1 ms 2396 KB ok
20 Correct 1 ms 2392 KB ok
21 Correct 1 ms 2396 KB ok
22 Correct 1 ms 2392 KB ok
23 Correct 1 ms 2396 KB ok
24 Correct 1 ms 2396 KB ok
25 Correct 0 ms 2396 KB ok
26 Correct 1 ms 2396 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB ok
2 Correct 1 ms 2396 KB ok
3 Correct 0 ms 2396 KB ok
4 Correct 0 ms 2396 KB ok
5 Correct 1 ms 2396 KB ok
6 Correct 1 ms 2392 KB ok
7 Correct 0 ms 2396 KB ok
8 Correct 1 ms 2396 KB ok
9 Correct 1 ms 2396 KB ok
10 Correct 1 ms 2396 KB ok
11 Correct 1 ms 2396 KB ok
12 Correct 1 ms 2396 KB ok
13 Correct 0 ms 2444 KB ok
14 Correct 1 ms 2396 KB ok
15 Correct 1 ms 2392 KB ok
16 Correct 0 ms 2396 KB ok
17 Correct 1 ms 2392 KB ok
18 Correct 1 ms 2396 KB ok
19 Correct 1 ms 2396 KB ok
20 Correct 1 ms 2396 KB ok
21 Correct 1 ms 2396 KB ok
22 Correct 1 ms 2392 KB ok
23 Correct 1 ms 2396 KB ok
24 Correct 1 ms 2392 KB ok
25 Correct 1 ms 2396 KB ok
26 Correct 1 ms 2396 KB ok
27 Correct 0 ms 2396 KB ok
28 Correct 1 ms 2396 KB ok
29 Correct 1 ms 2392 KB ok
30 Correct 1 ms 2392 KB ok
31 Correct 1 ms 2392 KB ok
32 Correct 1 ms 2396 KB ok
33 Correct 1 ms 2396 KB ok
34 Correct 1 ms 2396 KB ok
35 Correct 1 ms 2396 KB ok
36 Correct 1 ms 2396 KB ok
37 Correct 1 ms 2392 KB ok
38 Correct 1 ms 2396 KB ok
39 Correct 1 ms 2648 KB ok
40 Correct 1 ms 2396 KB ok
41 Correct 1 ms 2652 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB ok
2 Correct 1 ms 2396 KB ok
3 Correct 0 ms 2396 KB ok
4 Correct 0 ms 2396 KB ok
5 Correct 1 ms 2396 KB ok
6 Correct 1 ms 2392 KB ok
7 Correct 0 ms 2396 KB ok
8 Correct 1 ms 2396 KB ok
9 Correct 1 ms 2396 KB ok
10 Correct 1 ms 2396 KB ok
11 Correct 1 ms 2396 KB ok
12 Correct 1 ms 2396 KB ok
13 Correct 0 ms 2444 KB ok
14 Correct 1 ms 2396 KB ok
15 Correct 1 ms 2392 KB ok
16 Correct 0 ms 2396 KB ok
17 Correct 1 ms 2392 KB ok
18 Correct 1 ms 2396 KB ok
19 Correct 1 ms 2396 KB ok
20 Correct 1 ms 2396 KB ok
21 Correct 1 ms 2396 KB ok
22 Correct 1 ms 2392 KB ok
23 Correct 1 ms 2396 KB ok
24 Correct 1 ms 2392 KB ok
25 Correct 1 ms 2396 KB ok
26 Correct 1 ms 2396 KB ok
27 Correct 0 ms 2396 KB ok
28 Correct 1 ms 2396 KB ok
29 Correct 1 ms 2392 KB ok
30 Correct 1 ms 2392 KB ok
31 Correct 1 ms 2392 KB ok
32 Correct 1 ms 2396 KB ok
33 Correct 1 ms 2396 KB ok
34 Correct 1 ms 2396 KB ok
35 Correct 1 ms 2396 KB ok
36 Correct 1 ms 2396 KB ok
37 Correct 1 ms 2392 KB ok
38 Correct 1 ms 2396 KB ok
39 Correct 1 ms 2648 KB ok
40 Correct 1 ms 2396 KB ok
41 Correct 1 ms 2652 KB ok
42 Correct 56 ms 15244 KB ok
43 Correct 61 ms 16212 KB ok
44 Correct 30 ms 13144 KB ok
45 Correct 25 ms 12812 KB ok
46 Correct 47 ms 14344 KB ok
47 Correct 18 ms 12196 KB ok
48 Correct 20 ms 12120 KB ok
49 Correct 20 ms 12124 KB ok
50 Correct 27 ms 12124 KB ok
51 Correct 27 ms 13396 KB ok
52 Correct 20 ms 12196 KB ok
53 Correct 20 ms 12124 KB ok
54 Correct 20 ms 12124 KB ok
55 Correct 20 ms 12192 KB ok
56 Correct 20 ms 12196 KB ok
57 Correct 50 ms 16172 KB ok
58 Correct 58 ms 16796 KB ok
59 Correct 60 ms 17364 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB ok
2 Correct 1 ms 2396 KB ok
3 Correct 0 ms 2396 KB ok
4 Correct 0 ms 2396 KB ok
5 Correct 1 ms 2396 KB ok
6 Correct 0 ms 2396 KB ok
7 Correct 1 ms 2392 KB ok
8 Correct 2 ms 5220 KB ok
9 Correct 21 ms 12172 KB ok
10 Correct 260 ms 63524 KB ok
11 Correct 1 ms 2392 KB ok
12 Correct 0 ms 2396 KB ok
13 Correct 1 ms 2396 KB ok
14 Correct 1 ms 2396 KB ok
15 Correct 1 ms 2396 KB ok
16 Correct 1 ms 2396 KB ok
17 Correct 1 ms 2396 KB ok
18 Correct 0 ms 2444 KB ok
19 Correct 1 ms 2396 KB ok
20 Correct 1 ms 2392 KB ok
21 Correct 0 ms 2396 KB ok
22 Correct 1 ms 2392 KB ok
23 Correct 1 ms 2396 KB ok
24 Correct 1 ms 2396 KB ok
25 Correct 1 ms 2396 KB ok
26 Correct 1 ms 2396 KB ok
27 Correct 1 ms 2392 KB ok
28 Correct 1 ms 2396 KB ok
29 Correct 1 ms 2392 KB ok
30 Correct 1 ms 2396 KB ok
31 Correct 1 ms 2396 KB ok
32 Correct 0 ms 2396 KB ok
33 Correct 1 ms 2396 KB ok
34 Correct 1 ms 2392 KB ok
35 Correct 1 ms 2392 KB ok
36 Correct 1 ms 2392 KB ok
37 Correct 1 ms 2396 KB ok
38 Correct 1 ms 2396 KB ok
39 Correct 1 ms 2396 KB ok
40 Correct 1 ms 2396 KB ok
41 Correct 1 ms 2396 KB ok
42 Correct 1 ms 2392 KB ok
43 Correct 1 ms 2396 KB ok
44 Correct 1 ms 2648 KB ok
45 Correct 1 ms 2396 KB ok
46 Correct 1 ms 2652 KB ok
47 Correct 56 ms 15244 KB ok
48 Correct 61 ms 16212 KB ok
49 Correct 30 ms 13144 KB ok
50 Correct 25 ms 12812 KB ok
51 Correct 47 ms 14344 KB ok
52 Correct 18 ms 12196 KB ok
53 Correct 20 ms 12120 KB ok
54 Correct 20 ms 12124 KB ok
55 Correct 27 ms 12124 KB ok
56 Correct 27 ms 13396 KB ok
57 Correct 20 ms 12196 KB ok
58 Correct 20 ms 12124 KB ok
59 Correct 20 ms 12124 KB ok
60 Correct 20 ms 12192 KB ok
61 Correct 20 ms 12196 KB ok
62 Correct 50 ms 16172 KB ok
63 Correct 58 ms 16796 KB ok
64 Correct 60 ms 17364 KB ok
65 Correct 971 ms 114468 KB ok
66 Correct 608 ms 110676 KB ok
67 Correct 417 ms 84504 KB ok
68 Correct 317 ms 66128 KB ok
69 Correct 501 ms 77604 KB ok
70 Correct 631 ms 87268 KB ok
71 Correct 299 ms 65112 KB ok
72 Correct 250 ms 63524 KB ok
73 Correct 278 ms 63828 KB ok
74 Correct 285 ms 63828 KB ok
75 Correct 281 ms 63828 KB ok
76 Correct 472 ms 63568 KB ok
77 Correct 477 ms 63572 KB ok
78 Correct 386 ms 73808 KB ok
79 Correct 345 ms 67876 KB ok
80 Correct 315 ms 66644 KB ok
81 Correct 317 ms 66644 KB ok
82 Correct 361 ms 70432 KB ok
83 Correct 510 ms 82512 KB ok
84 Correct 282 ms 63792 KB ok
85 Correct 272 ms 63828 KB ok
86 Correct 273 ms 63780 KB ok
87 Correct 287 ms 64804 KB ok
88 Correct 270 ms 63736 KB ok
89 Correct 274 ms 63572 KB ok
90 Correct 280 ms 63780 KB ok
91 Correct 288 ms 63676 KB ok
92 Correct 384 ms 75296 KB ok
93 Correct 381 ms 77428 KB ok
94 Correct 310 ms 68120 KB ok
95 Correct 306 ms 66336 KB ok
96 Correct 300 ms 65240 KB ok
97 Correct 287 ms 64848 KB ok
98 Correct 288 ms 64292 KB ok
99 Correct 918 ms 129212 KB ok
100 Correct 915 ms 126800 KB ok
101 Correct 1050 ms 120452 KB ok
102 Correct 957 ms 126552 KB ok
103 Correct 1000 ms 137664 KB ok
104 Correct 1123 ms 141320 KB ok
105 Correct 1201 ms 144188 KB ok
106 Correct 1103 ms 147352 KB ok
107 Correct 1077 ms 146920 KB ok
108 Correct 436 ms 68948 KB ok
109 Correct 433 ms 68688 KB ok