oj.uz

Submission #937649

# Submission time Handle Problem Language Result Execution time Memory
937649 2024-03-04T10:10:53 Z Wansur Soccer Stadium (IOI23_soccer) C++17
61 / 100
 466 ms 308240 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define ent '\n'

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

typedef long long ll;
using namespace std;
struct seg{
    int m1,m2,sum,cnt;
};

const string out[2]={"NO\n","YES\n"};

const ll dx[]={0,1,0,-1,-1,1,1,-1};
const ll dy[]={1,0,-1,0,-1,1,-1,1};
const int mod=998244353;
const int md=1e9+7;
const int mx=2e3+12;
const bool T=0;

int dp[61][61][61][61];
bool used[2001][2001];
int pref[61][61];
int n;

int get(int i,int l,int r){
    if(!l)return pref[i][r];
    return pref[i][r]-pref[i][l-1];
}

void dfs(int x,int y){
    used[x][y]=1;
    for(int i=0;i<4;i++){
        int x1=dx[i]+x,y1=dy[i]+y;
        if(min(x1,y1)>=0 && max(x1,y1)<n && !used[x1][y1]){
            dfs(x1,y1);
        }
    }
}

int solve(int N, vector<vector<int>> a){

    int sum=0;
    n=N;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            sum+=!a[i][j];
            if(a[i][j]){
                used[i][j]=1;
            }
        }
    }
    bool ok=0;
    int pos=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(!used[i][j]){
                pos=i;
                if(ok)return 0;
                ok=1;
                dfs(i,j);
            }
        }
    }
    int l=-1,r=-1;
    int len=0,sg=0;
    vector<pair<int,int>> v;
    for(int i=pos;i<n;i++){
        int tl=-1,tr=-1,sum=0;
        for(int j=0;j<n;j++){
            if(!a[i][j]) {
                ok = 1;
                if(tl==-1){
                    tl=j;
                }
                tr=j;
                sum++;
            }
        }
        if(tl==-1)break;
        if(l==-1){
            l=tl,r=tr;
        }
        if(!(l<=tl && tr<=r || tl<=l && r<=tr) || sum!=tr-tl+1){
            return 0;
        }
        if(r-l+1 <= tr-tl+1){
            if(r-l+1 < tr-tl+1 && sg){
                return 0;
            }
        }
        else{
            sg=1;
        }
        l=tl,r=tr;
        v.push_back({tl,tr});
    }
    sort(v.begin(),v.end(),[](pair<int,int> a,pair<int,int> b){
        return a.s-a.f>b.s-b.f;
    });
    l=v[0].f,r=v[0].s;
    for(auto [tl,tr]: v){
        if(tl < l || tr > r){
            return 0;
        }
        l=tl, r=tr;
    }
    return sum;
}

int biggest_stadium(int N, vector<vector<int>> a) {
    n = N;
    if (n > 30) {
        return solve(N, a);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            pref[i][j] = a[i][j];
            if (j)pref[i][j] += pref[i][j - 1];
        }
    }
    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int l=0;l<n;l++){
                for(int r=0;r<n;r++){
                    dp[i][j][l][r]=-1e9;
                }
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int l=0;l<n;l++){
            for(int r=l;r<n;r++){
                if(a[i][r])break;
                ans=max(ans,r-l+1);
                dp[i][i][l][r]=r-l+1;
            }
        }
    }
    for(int len=2;len<=n;len++){
        for(int i=0;i+len-1<n;i++){
            int j=i+len-1;
            for(int len=1;len<=n;len++){
                for(int l=0;l+len-1<n;l++){
                    int r=l+len-1;
                    if(!get(i,l,r)){
                        for(int tl=l;tl>=0;tl--){
                            for(int tr=r;tr<n;tr++){
                                dp[i][j][l][r]=max(dp[i][j][l][r], dp[i+1][j][tl][tr] + r-l+1);
                            }
                        }
                    }
                    if(!get(j,l,r)){
                        for(int tl=l;tl>=0;tl--){
                            for(int tr=r;tr<n;tr++){
                                dp[i][j][l][r]=max(dp[i][j][l][r], dp[i][j-1][tl][tr] + r-l+1);
                            }
                        }
                    }
                    ans=max(ans,dp[i][j][l][r]);
                }
            }
        }
    }
    return ans;
}

Compilation message

soccer.cpp: In function 'int solve(int, std::vector<std::vector<int> >)':
soccer.cpp:87:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   87 |         if(!(l<=tl && tr<=r || tl<=l && r<=tr) || sum!=tr-tl+1){
      |              ~~~~~~^~~~~~~~
soccer.cpp:69:9: warning: unused variable 'len' [-Wunused-variable]
   69 |     int len=0,sg=0;
      |         ^~~

Subtask #0
0.0 / 0.0

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

Subtask #1
1.5 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB ok
2 Correct 1 ms 4444 KB ok
3 Correct 1 ms 10588 KB ok
4 Correct 2 ms 10588 KB ok
5 Correct 0 ms 2396 KB ok
6 Correct 1 ms 4444 KB ok
7 Partially correct 1 ms 1372 KB partial
8 Partially correct 28 ms 21084 KB partial
9 Partially correct 462 ms 302368 KB partial

Subtask #2
8.0 / 8.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB ok
2 Correct 1 ms 4444 KB ok
3 Correct 1 ms 4444 KB ok
4 Correct 1 ms 4444 KB ok
5 Correct 1 ms 4444 KB ok
6 Correct 1 ms 4444 KB ok
7 Correct 1 ms 4444 KB ok
8 Correct 1 ms 4440 KB ok
9 Correct 1 ms 4440 KB ok
10 Correct 1 ms 4468 KB ok
11 Correct 1 ms 4444 KB ok
12 Correct 1 ms 4440 KB ok
13 Correct 1 ms 4444 KB ok
14 Correct 1 ms 4444 KB ok
15 Correct 2 ms 8536 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 8540 KB ok
21 Correct 1 ms 8648 KB ok
22 Correct 2 ms 8540 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 6488 KB ok
2 Correct 1 ms 4444 KB ok
3 Correct 1 ms 4444 KB ok
4 Correct 1 ms 10588 KB ok
5 Correct 2 ms 10588 KB ok
6 Correct 1 ms 4444 KB ok
7 Correct 1 ms 4444 KB ok
8 Correct 1 ms 4444 KB ok
9 Correct 1 ms 4444 KB ok
10 Correct 1 ms 4440 KB ok
11 Correct 1 ms 4440 KB ok
12 Correct 1 ms 4468 KB ok
13 Correct 1 ms 4444 KB ok
14 Correct 1 ms 4440 KB ok
15 Correct 1 ms 4444 KB ok
16 Correct 1 ms 4444 KB ok
17 Correct 2 ms 8536 KB ok
18 Correct 1 ms 8540 KB ok
19 Correct 1 ms 8540 KB ok
20 Correct 1 ms 8540 KB ok
21 Correct 1 ms 8540 KB ok
22 Correct 1 ms 8540 KB ok
23 Correct 1 ms 8648 KB ok
24 Correct 2 ms 8540 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 8540 KB ok
30 Correct 22 ms 29188 KB ok
31 Correct 14 ms 29188 KB ok
32 Correct 8 ms 29020 KB ok
33 Correct 7 ms 29020 KB ok
34 Correct 8 ms 29016 KB ok
35 Correct 12 ms 29020 KB ok
36 Correct 6 ms 29152 KB ok
37 Correct 8 ms 29016 KB ok
38 Correct 8 ms 29176 KB ok
39 Correct 10 ms 29020 KB ok
40 Correct 22 ms 29128 KB ok
41 Correct 31 ms 29168 KB ok

Subtask #5
4.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB ok
2 Correct 1 ms 4444 KB ok
3 Correct 1 ms 4444 KB ok
4 Correct 1 ms 10588 KB ok
5 Correct 2 ms 10588 KB ok
6 Correct 1 ms 4444 KB ok
7 Correct 1 ms 4444 KB ok
8 Correct 1 ms 4444 KB ok
9 Correct 1 ms 4444 KB ok
10 Correct 1 ms 4440 KB ok
11 Correct 1 ms 4440 KB ok
12 Correct 1 ms 4468 KB ok
13 Correct 1 ms 4444 KB ok
14 Correct 1 ms 4440 KB ok
15 Correct 1 ms 4444 KB ok
16 Correct 1 ms 4444 KB ok
17 Correct 2 ms 8536 KB ok
18 Correct 1 ms 8540 KB ok
19 Correct 1 ms 8540 KB ok
20 Correct 1 ms 8540 KB ok
21 Correct 1 ms 8540 KB ok
22 Correct 1 ms 8540 KB ok
23 Correct 1 ms 8648 KB ok
24 Correct 2 ms 8540 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 8540 KB ok
30 Correct 22 ms 29188 KB ok
31 Correct 14 ms 29188 KB ok
32 Correct 8 ms 29020 KB ok
33 Correct 7 ms 29020 KB ok
34 Correct 8 ms 29016 KB ok
35 Correct 12 ms 29020 KB ok
36 Correct 6 ms 29152 KB ok
37 Correct 8 ms 29016 KB ok
38 Correct 8 ms 29176 KB ok
39 Correct 10 ms 29020 KB ok
40 Correct 22 ms 29128 KB ok
41 Correct 31 ms 29168 KB ok
42 Partially correct 25 ms 16728 KB partial
43 Partially correct 24 ms 13400 KB partial
44 Partially correct 27 ms 20312 KB partial
45 Partially correct 26 ms 20828 KB partial
46 Partially correct 25 ms 18780 KB partial
47 Partially correct 29 ms 21084 KB partial
48 Correct 21 ms 13400 KB ok
49 Partially correct 21 ms 14428 KB partial
50 Partially correct 21 ms 13904 KB partial
51 Partially correct 15 ms 5980 KB partial
52 Partially correct 17 ms 8028 KB partial
53 Partially correct 17 ms 6996 KB partial
54 Partially correct 17 ms 8028 KB partial
55 Partially correct 18 ms 9296 KB partial
56 Partially correct 20 ms 12376 KB partial
57 Partially correct 25 ms 17748 KB partial
58 Partially correct 23 ms 16976 KB partial
59 Partially correct 23 ms 15996 KB partial

Subtask #6
7.5 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB ok
2 Correct 1 ms 4444 KB ok
3 Correct 1 ms 4444 KB ok
4 Correct 1 ms 10588 KB ok
5 Correct 2 ms 10588 KB ok
6 Correct 0 ms 2396 KB ok
7 Correct 1 ms 4444 KB ok
8 Partially correct 1 ms 1372 KB partial
9 Partially correct 28 ms 21084 KB partial
10 Partially correct 462 ms 302368 KB partial
11 Correct 1 ms 4444 KB ok
12 Correct 1 ms 4444 KB ok
13 Correct 1 ms 4444 KB ok
14 Correct 1 ms 4444 KB ok
15 Correct 1 ms 4440 KB ok
16 Correct 1 ms 4440 KB ok
17 Correct 1 ms 4468 KB ok
18 Correct 1 ms 4444 KB ok
19 Correct 1 ms 4440 KB ok
20 Correct 1 ms 4444 KB ok
21 Correct 1 ms 4444 KB ok
22 Correct 2 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
27 Correct 1 ms 8540 KB ok
28 Correct 1 ms 8648 KB ok
29 Correct 2 ms 8540 KB ok
30 Correct 1 ms 8540 KB ok
31 Correct 1 ms 8540 KB ok
32 Correct 1 ms 8540 KB ok
33 Correct 1 ms 8540 KB ok
34 Correct 1 ms 8540 KB ok
35 Correct 22 ms 29188 KB ok
36 Correct 14 ms 29188 KB ok
37 Correct 8 ms 29020 KB ok
38 Correct 7 ms 29020 KB ok
39 Correct 8 ms 29016 KB ok
40 Correct 12 ms 29020 KB ok
41 Correct 6 ms 29152 KB ok
42 Correct 8 ms 29016 KB ok
43 Correct 8 ms 29176 KB ok
44 Correct 10 ms 29020 KB ok
45 Correct 22 ms 29128 KB ok
46 Correct 31 ms 29168 KB ok
47 Partially correct 25 ms 16728 KB partial
48 Partially correct 24 ms 13400 KB partial
49 Partially correct 27 ms 20312 KB partial
50 Partially correct 26 ms 20828 KB partial
51 Partially correct 25 ms 18780 KB partial
52 Partially correct 29 ms 21084 KB partial
53 Correct 21 ms 13400 KB ok
54 Partially correct 21 ms 14428 KB partial
55 Partially correct 21 ms 13904 KB partial
56 Partially correct 15 ms 5980 KB partial
57 Partially correct 17 ms 8028 KB partial
58 Partially correct 17 ms 6996 KB partial
59 Partially correct 17 ms 8028 KB partial
60 Partially correct 18 ms 9296 KB partial
61 Partially correct 20 ms 12376 KB partial
62 Partially correct 25 ms 17748 KB partial
63 Partially correct 23 ms 16976 KB partial
64 Partially correct 23 ms 15996 KB partial
65 Partially correct 398 ms 237780 KB partial
66 Partially correct 251 ms 57936 KB partial
67 Partially correct 286 ms 58008 KB partial
68 Partially correct 466 ms 306880 KB partial
69 Partially correct 436 ms 298484 KB partial
70 Partially correct 450 ms 287380 KB partial
71 Partially correct 439 ms 307024 KB partial
72 Partially correct 442 ms 308240 KB partial
73 Correct 397 ms 183380 KB ok
74 Correct 349 ms 185800 KB ok
75 Partially correct 347 ms 185440 KB partial
76 Partially correct 346 ms 183120 KB partial
77 Partially correct 344 ms 182956 KB partial
78 Partially correct 235 ms 57988 KB partial
79 Partially correct 234 ms 57976 KB partial
80 Partially correct 236 ms 57972 KB partial
81 Partially correct 237 ms 57980 KB partial
82 Partially correct 232 ms 57836 KB partial
83 Partially correct 240 ms 57940 KB partial
84 Partially correct 265 ms 80692 KB partial
85 Partially correct 241 ms 72080 KB partial
86 Partially correct 261 ms 91784 KB partial
87 Partially correct 260 ms 95056 KB partial
88 Partially correct 333 ms 158904 KB partial
89 Partially correct 452 ms 285052 KB partial
90 Partially correct 400 ms 227556 KB partial
91 Partially correct 438 ms 269484 KB partial
92 Partially correct 237 ms 58884 KB partial
93 Partially correct 246 ms 58968 KB partial
94 Partially correct 236 ms 58964 KB partial
95 Partially correct 235 ms 58848 KB partial
96 Partially correct 240 ms 58960 KB partial
97 Partially correct 234 ms 58916 KB partial
98 Partially correct 234 ms 58960 KB partial
99 Partially correct 234 ms 58916 KB partial
100 Partially correct 404 ms 246672 KB partial
101 Partially correct 256 ms 87128 KB partial
102 Partially correct 262 ms 90452 KB partial
103 Partially correct 401 ms 233552 KB partial
104 Partially correct 263 ms 100176 KB partial
105 Partially correct 269 ms 104016 KB partial
106 Partially correct 364 ms 203716 KB partial
107 Partially correct 347 ms 186720 KB partial
108 Partially correct 239 ms 59020 KB partial
109 Partially correct 244 ms 51896 KB partial