oj.uz

Submission #842420

# Submission time Handle Problem Language Result Execution time Memory
842420 2023-09-02T21:03:03 Z firewater Soccer Stadium (IOI23_soccer) C++17
64 / 100
 4500 ms 146724 KB 
#include "soccer.h"
#include<bits/stdc++.h>
#define fs first
#define sn second
#define mp make_pair
#define MX 2023
using namespace std;
int n,now,ans,sl,sr,a[MX][MX],sum[MX][MX],stl[MX][20],str[MX][20],fl[MX][MX],fr[MX][MX];
pair<int,pair<int,int> >f[MX][MX];
int get(int A[MX][20],int l,int r)
{
    int k=__lg(r-l+1);
    return min(A[l][k],A[r-(1<<k)+1][k]);
}
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][j-1]+a[i][j];
        }
    for(int i=1;i<=n;++i){
        now=1;
        for(int j=1;j<=n;++j){
            if(a[i][j])now=j+1;
            else fl[i][j]=j-now+1;
        }
        now=n;
        for(int j=n;j>0;--j){
            if(a[i][j])now=j-1;
            else fr[i][j]=now-j+1;
        }
    }
    for(int j=1;j<=n;++j){
        for(int i=1;i<=n;++i){
            stl[i][0]=fl[i][j];
            str[i][0]=fr[i][j];
        }
        for(int k=1;k<=17;++k){
            for(int i=1;i<=n;++i){
                stl[i][k]=min(stl[i][k-1],(i+(1<<k-1)<=n?stl[i+(1<<k-1)][k-1]:n));
                str[i][k]=min(str[i][k-1],(i+(1<<k-1)<=n?str[i+(1<<k-1)][k-1]:n));
            }
        }
        for(int i=1;i<=n;++i)
            for(int k=i;k<=n;++k)
                f[i][k]=mp(0,mp(0,0));
        for(int i=1;i<=n;++i)
            f[i][i]=mp(max(0,fl[i][j]+fr[i][j]-1),mp(fl[i][j],fr[i][j]));
        for(int len=1;len<=n;++len)
            for(int i=1;i<=n-len+1;++i){
                int k=i+len-1;
                ans=max(ans,f[i][k].fs);
                if(i>1){
                    sl=min(f[i][k].sn.fs,fl[i-1][j]);
                    sr=min(f[i][k].sn.sn,fr[i-1][j]);
                    f[i-1][k]=max(f[i-1][k],mp(f[i][k].fs+max(sl+sr-1,0),mp(sl,sr)));
                }
                if(k<n){
                    sl=min(f[i][k].sn.fs,fl[k+1][j]);
                    sr=min(f[i][k].sn.sn,fr[k+1][j]);
                    f[i][k+1]=max(f[i][k+1],mp(f[i][k].fs+max(sl+sr-1,0),mp(sl,sr)));
                }
            }
    }
    return ans;
}

Compilation message

soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:43:51: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   43 |                 stl[i][k]=min(stl[i][k-1],(i+(1<<k-1)<=n?stl[i+(1<<k-1)][k-1]:n));
      |                                                  ~^~
soccer.cpp:43:69: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   43 |                 stl[i][k]=min(stl[i][k-1],(i+(1<<k-1)<=n?stl[i+(1<<k-1)][k-1]:n));
      |                                                                    ~^~
soccer.cpp:44:51: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   44 |                 str[i][k]=min(str[i][k-1],(i+(1<<k-1)<=n?str[i+(1<<k-1)][k-1]:n));
      |                                                  ~^~
soccer.cpp:44:69: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   44 |                 str[i][k]=min(str[i][k-1],(i+(1<<k-1)<=n?str[i+(1<<k-1)][k-1]:n));
      |                                                                    ~^~

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB ok
2 Correct 1 ms 8540 KB ok
3 Correct 1 ms 10588 KB ok
4 Correct 1 ms 10588 KB ok
5 Correct 2 ms 8624 KB ok
6 Correct 1 ms 8536 KB ok
7 Correct 7 ms 15196 KB ok
8 Correct 455 ms 38816 KB ok
9 Execution timed out 4545 ms 146724 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB ok
2 Correct 1 ms 8536 KB ok
3 Correct 1 ms 8540 KB ok
4 Correct 1 ms 10588 KB ok
5 Correct 1 ms 10588 KB ok
6 Correct 1 ms 8536 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 1 ms 8540 KB ok
9 Correct 1 ms 8540 KB ok
10 Correct 1 ms 8540 KB ok
11 Correct 1 ms 8540 KB ok
12 Correct 1 ms 8536 KB ok
13 Correct 1 ms 8540 KB ok
14 Correct 1 ms 8540 KB ok
15 Correct 1 ms 8540 KB ok
16 Correct 1 ms 8540 KB ok
17 Correct 1 ms 8540 KB ok
18 Correct 1 ms 8540 KB ok
19 Correct 1 ms 8540 KB ok
20 Correct 1 ms 8680 KB ok
21 Correct 1 ms 8540 KB ok
22 Correct 1 ms 8540 KB ok
23 Correct 1 ms 8676 KB ok
24 Correct 1 ms 8536 KB ok
25 Correct 1 ms 8540 KB ok
26 Correct 1 ms 8540 KB ok
27 Correct 1 ms 8540 KB ok
28 Correct 1 ms 8540 KB ok
29 Correct 1 ms 8536 KB ok
30 Correct 2 ms 12892 KB ok
31 Correct 2 ms 12892 KB ok
32 Correct 2 ms 12888 KB ok
33 Correct 2 ms 12888 KB ok
34 Correct 2 ms 12892 KB ok
35 Correct 2 ms 12892 KB ok
36 Correct 2 ms 12888 KB ok
37 Correct 2 ms 12712 KB ok
38 Correct 2 ms 12888 KB ok
39 Correct 2 ms 12892 KB ok
40 Correct 2 ms 12892 KB ok
41 Correct 2 ms 13144 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB ok
2 Correct 1 ms 8536 KB ok
3 Correct 1 ms 8540 KB ok
4 Correct 1 ms 10588 KB ok
5 Correct 1 ms 10588 KB ok
6 Correct 1 ms 8536 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 1 ms 8540 KB ok
9 Correct 1 ms 8540 KB ok
10 Correct 1 ms 8540 KB ok
11 Correct 1 ms 8540 KB ok
12 Correct 1 ms 8536 KB ok
13 Correct 1 ms 8540 KB ok
14 Correct 1 ms 8540 KB ok
15 Correct 1 ms 8540 KB ok
16 Correct 1 ms 8540 KB ok
17 Correct 1 ms 8540 KB ok
18 Correct 1 ms 8540 KB ok
19 Correct 1 ms 8540 KB ok
20 Correct 1 ms 8680 KB ok
21 Correct 1 ms 8540 KB ok
22 Correct 1 ms 8540 KB ok
23 Correct 1 ms 8676 KB ok
24 Correct 1 ms 8536 KB ok
25 Correct 1 ms 8540 KB ok
26 Correct 1 ms 8540 KB ok
27 Correct 1 ms 8540 KB ok
28 Correct 1 ms 8540 KB ok
29 Correct 1 ms 8536 KB ok
30 Correct 2 ms 12892 KB ok
31 Correct 2 ms 12892 KB ok
32 Correct 2 ms 12888 KB ok
33 Correct 2 ms 12888 KB ok
34 Correct 2 ms 12892 KB ok
35 Correct 2 ms 12892 KB ok
36 Correct 2 ms 12888 KB ok
37 Correct 2 ms 12712 KB ok
38 Correct 2 ms 12888 KB ok
39 Correct 2 ms 12892 KB ok
40 Correct 2 ms 12892 KB ok
41 Correct 2 ms 13144 KB ok
42 Correct 472 ms 38224 KB ok
43 Correct 480 ms 38328 KB ok
44 Correct 455 ms 38324 KB ok
45 Correct 452 ms 38324 KB ok
46 Correct 480 ms 38324 KB ok
47 Correct 445 ms 38324 KB ok
48 Correct 450 ms 38328 KB ok
49 Correct 458 ms 38324 KB ok
50 Correct 442 ms 38232 KB ok
51 Correct 456 ms 38324 KB ok
52 Correct 470 ms 36272 KB ok
53 Correct 471 ms 34228 KB ok
54 Correct 466 ms 34456 KB ok
55 Correct 486 ms 36272 KB ok
56 Correct 468 ms 34140 KB ok
57 Correct 437 ms 38484 KB ok
58 Correct 439 ms 38328 KB ok
59 Correct 439 ms 38336 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB ok
2 Correct 1 ms 8536 KB ok
3 Correct 1 ms 8540 KB ok
4 Correct 1 ms 10588 KB ok
5 Correct 1 ms 10588 KB ok
6 Correct 2 ms 8624 KB ok
7 Correct 1 ms 8536 KB ok
8 Correct 7 ms 15196 KB ok
9 Correct 455 ms 38816 KB ok
10 Execution timed out 4545 ms 146724 KB Time limit exceeded
11 Halted 0 ms 0 KB -