oj.uz

Submission #846983

# Submission time Handle Problem Language Result Execution time Memory
846983 2023-09-08T20:11:41 Z firewater Soccer Stadium (IOI23_soccer) C++17
54 / 100
 4500 ms 112936 KB 
#include "soccer.h"
#include<bits/stdc++.h>
#define fs first
#define sn second
#define MX 2020
using namespace std;
int n,ans,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 f[{x,{L,R}}]=num;
    if(x>sav.fs)return f[{x,{L,R}}]=solve(sav.fs,L,R);

    for(int li=L,ri=L;li<=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;
        k=find(x,li,ri);
        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){
        sav=find(i,1,n);
        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:49:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |             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 1 ms 2396 KB ok
3 Correct 0 ms 2396 KB ok
4 Correct 1 ms 2396 KB ok
5 Correct 1 ms 2392 KB ok
6 Correct 1 ms 2396 KB ok
7 Correct 2 ms 4956 KB ok
8 Correct 18 ms 12124 KB ok
9 Correct 251 ms 63776 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB ok
2 Correct 1 ms 2396 KB ok
3 Correct 1 ms 2396 KB ok
4 Correct 1 ms 2392 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 0 ms 2396 KB ok
9 Correct 0 ms 2396 KB ok
10 Correct 1 ms 2392 KB ok
11 Correct 1 ms 2392 KB ok
12 Correct 1 ms 2396 KB ok
13 Correct 1 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 1 ms 2396 KB ok
4 Correct 1 ms 2396 KB ok
5 Correct 1 ms 2392 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 0 ms 2396 KB ok
10 Correct 0 ms 2396 KB ok
11 Correct 1 ms 2392 KB ok
12 Correct 1 ms 2392 KB ok
13 Correct 1 ms 2396 KB ok
14 Correct 1 ms 2396 KB ok
15 Correct 0 ms 2392 KB ok
16 Correct 1 ms 2396 KB ok
17 Correct 1 ms 2392 KB ok
18 Correct 1 ms 2396 KB ok
19 Correct 0 ms 2396 KB ok
20 Correct 1 ms 2396 KB ok
21 Correct 1 ms 2396 KB ok
22 Correct 1 ms 2396 KB ok
23 Correct 1 ms 2396 KB ok
24 Correct 0 ms 2392 KB ok
25 Correct 1 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 1 ms 2396 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 2392 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 2396 KB ok
12 Correct 0 ms 2396 KB ok
13 Correct 1 ms 2392 KB ok
14 Correct 1 ms 2392 KB ok
15 Correct 1 ms 2396 KB ok
16 Correct 1 ms 2396 KB ok
17 Correct 0 ms 2392 KB ok
18 Correct 1 ms 2396 KB ok
19 Correct 1 ms 2392 KB ok
20 Correct 1 ms 2396 KB ok
21 Correct 0 ms 2396 KB ok
22 Correct 1 ms 2396 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 0 ms 2392 KB ok
27 Correct 1 ms 2396 KB ok
28 Correct 1 ms 2396 KB ok
29 Correct 1 ms 2392 KB ok
30 Correct 1 ms 2652 KB ok
31 Correct 1 ms 2652 KB ok
32 Correct 1 ms 2652 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 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 2652 KB ok

Subtask #5
0.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 1 ms 2396 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 2392 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 2396 KB ok
12 Correct 0 ms 2396 KB ok
13 Correct 1 ms 2392 KB ok
14 Correct 1 ms 2392 KB ok
15 Correct 1 ms 2396 KB ok
16 Correct 1 ms 2396 KB ok
17 Correct 0 ms 2392 KB ok
18 Correct 1 ms 2396 KB ok
19 Correct 1 ms 2392 KB ok
20 Correct 1 ms 2396 KB ok
21 Correct 0 ms 2396 KB ok
22 Correct 1 ms 2396 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 0 ms 2392 KB ok
27 Correct 1 ms 2396 KB ok
28 Correct 1 ms 2396 KB ok
29 Correct 1 ms 2392 KB ok
30 Correct 1 ms 2652 KB ok
31 Correct 1 ms 2652 KB ok
32 Correct 1 ms 2652 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 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 2652 KB ok
42 Correct 126 ms 23808 KB ok
43 Correct 92 ms 21680 KB ok
44 Correct 1650 ms 72060 KB ok
45 Execution timed out 4541 ms 112936 KB Time limit exceeded
46 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 1 ms 2396 KB ok
3 Correct 1 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 1 ms 2396 KB ok
8 Correct 2 ms 4956 KB ok
9 Correct 18 ms 12124 KB ok
10 Correct 251 ms 63776 KB ok
11 Correct 1 ms 2396 KB ok
12 Correct 1 ms 2392 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 0 ms 2396 KB ok
17 Correct 0 ms 2396 KB ok
18 Correct 1 ms 2392 KB ok
19 Correct 1 ms 2392 KB ok
20 Correct 1 ms 2396 KB ok
21 Correct 1 ms 2396 KB ok
22 Correct 0 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 0 ms 2396 KB ok
27 Correct 1 ms 2396 KB ok
28 Correct 1 ms 2396 KB ok
29 Correct 1 ms 2396 KB ok
30 Correct 1 ms 2396 KB ok
31 Correct 0 ms 2392 KB ok
32 Correct 1 ms 2396 KB ok
33 Correct 1 ms 2396 KB ok
34 Correct 1 ms 2392 KB ok
35 Correct 1 ms 2652 KB ok
36 Correct 1 ms 2652 KB ok
37 Correct 1 ms 2652 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 2396 KB ok
43 Correct 1 ms 2396 KB ok
44 Correct 1 ms 2396 KB ok
45 Correct 1 ms 2396 KB ok
46 Correct 1 ms 2652 KB ok
47 Correct 126 ms 23808 KB ok
48 Correct 92 ms 21680 KB ok
49 Correct 1650 ms 72060 KB ok
50 Execution timed out 4541 ms 112936 KB Time limit exceeded
51 Halted 0 ms 0 KB -