oj.uz

답안 #842462

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
842462 2023-09-02T22:52:41 Z firewater 축구 경기장 (IOI23_soccer) C++17
70 / 100
 4500 ms 144716 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,l,r,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],sav;
vector<pair<int,int> >d[MX];
int getl(int l,int r)
{
    int k=__lg(r-l+1);
    return min(stl[l][k],stl[r-(1<<k)+1][k]);
}
int getr(int l,int r)
{
    int k=__lg(r-l+1);
    return min(str[l][k],str[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<=11;++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)
            d[i].clear();
        for(int i=1;i<=n;++i){
            if(i>1&&fl[i-1][j]>=fl[i][j]&&fr[i-1][j]>=fr[i][j]&&(!(fl[i-1][j]==fl[i][j]&&fr[i-1][j]==fr[i][j])))continue;
            if(i<n&&fl[i+1][j]>=fl[i][j]&&fr[i+1][j]>=fr[i][j])continue;
            f[i][i]=mp(max(0,fl[i][j]+fr[i][j]-1),mp(fl[i][j],fr[i][j]));
            d[1].push_back(mp(i,i));
        }
        for(int len=1;len<=n;++len){
            int i,k;
            for(int g=0;g<d[len].size();++g){
                i=d[len][g].fs;k=d[len][g].sn;
                sl=f[i][k].sn.fs;
                sr=f[i][k].sn.sn;
                // if(j==5)
                // printf("%d %d %d %d              (%d %d)\n",j,i,k,f[i][k].fs,sl,sr);
                if(sl+sr<1)continue;
                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]);
                    if(sl+sr>0){
                        l=1;r=i-1;
                        while(l<r){
                            int mid=l+r>>1;
                            if(getl(mid,i-1)>=sl&&getr(mid,i-1)>=sr)r=mid;
                            else l=mid+1;
                        }
                        // printf("%d %d %d:%d ----->>>> %d %d:%d          (%d %d)\n",j,i,k,f[i][k].fs,l,k,f[i][k].fs+max(sr+sl-1,0)*(i-l),sl,sr);
                        sav=mp(f[i][k].fs+max(sr+sl-1,0)*(i-l),mp(sl,sr));
                        if(sav.fs>0&&sav>f[l][k]){
                            if(f[l][k].fs==0)d[k-l+1].push_back(mp(l,k));
                            f[l][k]=sav;
                        }
                    }
                }
                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]);
                    // printf("%d %d\n",fl[k+1][j],fr[k+1][j]);
                    if(sl+sr>0){
                        l=k+1;r=n;
                        while(l<r){
                            // printf("%d %d\n",l,r);
                            int mid=l+r+1>>1;
                            if(getl(k+1,mid)>=sl&&getr(k+1,mid)>=sr)l=mid;
                            else r=mid-1;
                        }
                        // printf("%d %d %d:%d ----->>>> %d %d:%d          (%d %d)\n",j,i,k,f[i][k].fs,i,l,f[i][k].fs+max(sr+sl-1,0)*(l-k),sl,sr);
                        sav=mp(f[i][k].fs+max(sr+sl-1,0)*(l-k),mp(sl,sr));
                        if(sav.fs>0&&sav>f[i][l]){
                            if(f[i][l].fs==0)d[l-i+1].push_back(mp(i,l));
                            f[i][l]=sav;
                        }
                    }
                }
                f[i][k]=mp(0,mp(0,0));
            }
            // 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:49:51: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   49 |                 stl[i][k]=min(stl[i][k-1],(i+(1<<k-1)<=n?stl[i+(1<<k-1)][k-1]:n));
      |                                                  ~^~
soccer.cpp:49:69: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   49 |                 stl[i][k]=min(stl[i][k-1],(i+(1<<k-1)<=n?stl[i+(1<<k-1)][k-1]:n));
      |                                                                    ~^~
soccer.cpp:50:51: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   50 |                 str[i][k]=min(str[i][k-1],(i+(1<<k-1)<=n?str[i+(1<<k-1)][k-1]:n));
      |                                                  ~^~
soccer.cpp:50:69: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   50 |                 str[i][k]=min(str[i][k-1],(i+(1<<k-1)<=n?str[i+(1<<k-1)][k-1]:n));
      |                                                                    ~^~
soccer.cpp:63:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |             for(int g=0;g<d[len].size();++g){
      |                         ~^~~~~~~~~~~~~~
soccer.cpp:78:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |                             int mid=l+r>>1;
      |                                     ~^~
soccer.cpp:98:40: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |                             int mid=l+r+1>>1;
      |                                     ~~~^~

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8536 KB ok

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8536 KB ok
2 Correct 1 ms 8536 KB ok
3 Correct 1 ms 10840 KB ok
4 Correct 1 ms 10584 KB ok
5 Correct 1 ms 8792 KB ok
6 Correct 1 ms 8536 KB ok
7 Correct 3 ms 15196 KB ok
8 Correct 28 ms 30040 KB ok
9 Correct 406 ms 98928 KB ok

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8536 KB ok
2 Correct 1 ms 8536 KB ok
3 Correct 1 ms 8536 KB ok
4 Correct 1 ms 8540 KB ok
5 Correct 1 ms 8536 KB ok
6 Correct 1 ms 8540 KB ok
7 Correct 1 ms 8536 KB ok
8 Correct 1 ms 8540 KB ok
9 Correct 1 ms 8536 KB ok
10 Correct 1 ms 8536 KB ok
11 Correct 1 ms 8536 KB ok
12 Correct 1 ms 8540 KB ok
13 Correct 1 ms 8540 KB ok

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8536 KB ok
2 Correct 1 ms 8536 KB ok
3 Correct 1 ms 8536 KB ok
4 Correct 1 ms 8536 KB ok
5 Correct 1 ms 8540 KB ok
6 Correct 1 ms 8536 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 1 ms 8536 KB ok
9 Correct 1 ms 8540 KB ok
10 Correct 1 ms 8536 KB ok
11 Correct 1 ms 8536 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 10584 KB ok
16 Correct 1 ms 10588 KB ok
17 Correct 1 ms 10584 KB ok
18 Correct 1 ms 10584 KB ok
19 Correct 2 ms 10584 KB ok
20 Correct 2 ms 10588 KB ok
21 Correct 1 ms 10584 KB ok
22 Correct 2 ms 10584 KB ok
23 Correct 1 ms 10584 KB ok
24 Correct 1 ms 10584 KB ok
25 Correct 2 ms 10588 KB ok
26 Correct 2 ms 10584 KB ok

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8536 KB ok
2 Correct 1 ms 8536 KB ok
3 Correct 1 ms 8536 KB ok
4 Correct 1 ms 10840 KB ok
5 Correct 1 ms 10584 KB ok
6 Correct 1 ms 8536 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 1 ms 8536 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 8536 KB ok
13 Correct 1 ms 8536 KB ok
14 Correct 1 ms 8536 KB ok
15 Correct 1 ms 8540 KB ok
16 Correct 1 ms 8540 KB ok
17 Correct 1 ms 10584 KB ok
18 Correct 1 ms 10588 KB ok
19 Correct 1 ms 10584 KB ok
20 Correct 1 ms 10584 KB ok
21 Correct 2 ms 10584 KB ok
22 Correct 2 ms 10588 KB ok
23 Correct 1 ms 10584 KB ok
24 Correct 2 ms 10584 KB ok
25 Correct 1 ms 10584 KB ok
26 Correct 1 ms 10584 KB ok
27 Correct 2 ms 10588 KB ok
28 Correct 2 ms 10584 KB ok
29 Correct 1 ms 10584 KB ok
30 Correct 2 ms 12892 KB ok
31 Correct 2 ms 13144 KB ok
32 Correct 2 ms 12888 KB ok
33 Correct 2 ms 12888 KB ok
34 Correct 2 ms 12888 KB ok
35 Correct 2 ms 12892 KB ok
36 Correct 2 ms 12892 KB ok
37 Correct 2 ms 12888 KB ok
38 Correct 2 ms 12888 KB ok
39 Correct 2 ms 12888 KB ok
40 Correct 2 ms 12892 KB ok
41 Correct 2 ms 12888 KB ok

Subtask #5
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8536 KB ok
2 Correct 1 ms 8536 KB ok
3 Correct 1 ms 8536 KB ok
4 Correct 1 ms 10840 KB ok
5 Correct 1 ms 10584 KB ok
6 Correct 1 ms 8536 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 1 ms 8536 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 8536 KB ok
13 Correct 1 ms 8536 KB ok
14 Correct 1 ms 8536 KB ok
15 Correct 1 ms 8540 KB ok
16 Correct 1 ms 8540 KB ok
17 Correct 1 ms 10584 KB ok
18 Correct 1 ms 10588 KB ok
19 Correct 1 ms 10584 KB ok
20 Correct 1 ms 10584 KB ok
21 Correct 2 ms 10584 KB ok
22 Correct 2 ms 10588 KB ok
23 Correct 1 ms 10584 KB ok
24 Correct 2 ms 10584 KB ok
25 Correct 1 ms 10584 KB ok
26 Correct 1 ms 10584 KB ok
27 Correct 2 ms 10588 KB ok
28 Correct 2 ms 10584 KB ok
29 Correct 1 ms 10584 KB ok
30 Correct 2 ms 12892 KB ok
31 Correct 2 ms 13144 KB ok
32 Correct 2 ms 12888 KB ok
33 Correct 2 ms 12888 KB ok
34 Correct 2 ms 12888 KB ok
35 Correct 2 ms 12892 KB ok
36 Correct 2 ms 12892 KB ok
37 Correct 2 ms 12888 KB ok
38 Correct 2 ms 12888 KB ok
39 Correct 2 ms 12888 KB ok
40 Correct 2 ms 12892 KB ok
41 Correct 2 ms 12888 KB ok
42 Correct 111 ms 38232 KB ok
43 Correct 72 ms 38476 KB ok
44 Correct 272 ms 38400 KB ok
45 Correct 340 ms 38480 KB ok
46 Correct 187 ms 38340 KB ok
47 Correct 34 ms 38232 KB ok
48 Correct 745 ms 35520 KB ok
49 Correct 866 ms 35624 KB ok
50 Correct 41 ms 38344 KB ok
51 Correct 56 ms 38236 KB ok
52 Correct 194 ms 26772 KB ok
53 Correct 41 ms 24112 KB ok
54 Correct 157 ms 30392 KB ok
55 Correct 302 ms 33576 KB ok
56 Correct 47 ms 27996 KB ok
57 Correct 1028 ms 33020 KB ok
58 Correct 1111 ms 32764 KB ok
59 Correct 1091 ms 32752 KB ok

Subtask #6
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8536 KB ok
2 Correct 1 ms 8536 KB ok
3 Correct 1 ms 8536 KB ok
4 Correct 1 ms 10840 KB ok
5 Correct 1 ms 10584 KB ok
6 Correct 1 ms 8792 KB ok
7 Correct 1 ms 8536 KB ok
8 Correct 3 ms 15196 KB ok
9 Correct 28 ms 30040 KB ok
10 Correct 406 ms 98928 KB ok
11 Correct 1 ms 8536 KB ok
12 Correct 1 ms 8540 KB ok
13 Correct 1 ms 8536 KB ok
14 Correct 1 ms 8540 KB ok
15 Correct 1 ms 8536 KB ok
16 Correct 1 ms 8540 KB ok
17 Correct 1 ms 8536 KB ok
18 Correct 1 ms 8536 KB ok
19 Correct 1 ms 8536 KB ok
20 Correct 1 ms 8540 KB ok
21 Correct 1 ms 8540 KB ok
22 Correct 1 ms 10584 KB ok
23 Correct 1 ms 10588 KB ok
24 Correct 1 ms 10584 KB ok
25 Correct 1 ms 10584 KB ok
26 Correct 2 ms 10584 KB ok
27 Correct 2 ms 10588 KB ok
28 Correct 1 ms 10584 KB ok
29 Correct 2 ms 10584 KB ok
30 Correct 1 ms 10584 KB ok
31 Correct 1 ms 10584 KB ok
32 Correct 2 ms 10588 KB ok
33 Correct 2 ms 10584 KB ok
34 Correct 1 ms 10584 KB ok
35 Correct 2 ms 12892 KB ok
36 Correct 2 ms 13144 KB ok
37 Correct 2 ms 12888 KB ok
38 Correct 2 ms 12888 KB ok
39 Correct 2 ms 12888 KB ok
40 Correct 2 ms 12892 KB ok
41 Correct 2 ms 12892 KB ok
42 Correct 2 ms 12888 KB ok
43 Correct 2 ms 12888 KB ok
44 Correct 2 ms 12888 KB ok
45 Correct 2 ms 12892 KB ok
46 Correct 2 ms 12888 KB ok
47 Correct 111 ms 38232 KB ok
48 Correct 72 ms 38476 KB ok
49 Correct 272 ms 38400 KB ok
50 Correct 340 ms 38480 KB ok
51 Correct 187 ms 38340 KB ok
52 Correct 34 ms 38232 KB ok
53 Correct 745 ms 35520 KB ok
54 Correct 866 ms 35624 KB ok
55 Correct 41 ms 38344 KB ok
56 Correct 56 ms 38236 KB ok
57 Correct 194 ms 26772 KB ok
58 Correct 41 ms 24112 KB ok
59 Correct 157 ms 30392 KB ok
60 Correct 302 ms 33576 KB ok
61 Correct 47 ms 27996 KB ok
62 Correct 1028 ms 33020 KB ok
63 Correct 1111 ms 32764 KB ok
64 Correct 1091 ms 32752 KB ok
65 Correct 2005 ms 144176 KB ok
66 Correct 509 ms 144208 KB ok
67 Correct 433 ms 143964 KB ok
68 Execution timed out 4539 ms 144716 KB Time limit exceeded
69 Halted 0 ms 0 KB -