oj.uz

Submission #939403

# Submission time Handle Problem Language Result Execution time Memory
939403 2024-03-06T10:30:11 Z Wansur Soccer Stadium (IOI23_soccer) C++17
65.5 / 100
 2360 ms 523244 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define ent '\n'

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[512][512][512];
int pref[mx][mx];
int a[mx][mx];
int n;

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

int biggest_stadium(int N, vector<vector<int>> B) {
    n = N;
    if (n > 500) {
        return 0;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            a[i][j]=B[i][j];
            pref[i][j]=a[i][j];
            if(j) pref[i][j]+=pref[i][j-1];
        }
    }
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            for(int k=0;k<=n;k++){
                dp[i][j][k]=-1e9;
            }
        }
    }
    int ans=0;

    for(int len=n;len>=1;len--){
        for(int l=0;l+len-1<n;l++){
            int r=l+len-1;
            for(int i=0;i<n;i++){
                if(get(i,l,r)) {
                    continue;
                }
                int j=i;
                while(j<n-1 && !get(j+1,l,r)){
                    j++;
                }
                dp[i][l][r]=(j-i+1)*(r-l+1);
                if(l>0){
                    for(int s=i;s<=j;s++){
                        if(get(s,l-1,r)){
                            continue;
                        }
                        int t=s;
                        while(t<n-1 && !get(t+1,l-1,r)){
                            t++;
                        }
                        dp[i][l][r]=max(dp[i][l][r], dp[s][l-1][r] + ((j-i+1) - (t-s+1)) * (r-l+1));
                        s=t;
                    }
                }
                if(r<n-1){
                    for(int s=i;s<=j;s++){
                        if(get(s,l,r+1)){
                            continue;
                        }
                        int t=s;
                        while(t<n-1 && !get(t+1,l,r+1)){
                            t++;
                        }
                        dp[i][l][r]=max(dp[i][l][r], dp[s][l][r+1] + ((j-i+1) - (t-s+1)) * (r-l+1));
                        s=t;
                    }
                }
                ans=max(ans,dp[i][l][r]);
                i=j;
            }
        }

    }
    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
1.5 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB ok
2 Correct 1 ms 6492 KB ok
3 Correct 2 ms 12636 KB ok
4 Correct 3 ms 14684 KB ok
5 Correct 1 ms 4444 KB ok
6 Correct 1 ms 6492 KB ok
7 Correct 42 ms 111340 KB ok
8 Correct 513 ms 522064 KB ok
9 Partially correct 227 ms 31824 KB partial

Subtask #2
8.0 / 8.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB ok
2 Correct 1 ms 6488 KB ok
3 Correct 1 ms 6492 KB ok
4 Correct 2 ms 12636 KB ok
5 Correct 3 ms 14684 KB ok
6 Correct 1 ms 6488 KB ok
7 Correct 1 ms 6488 KB ok
8 Correct 1 ms 6492 KB ok
9 Correct 1 ms 6492 KB ok
10 Correct 1 ms 6488 KB ok
11 Correct 1 ms 6488 KB ok
12 Correct 1 ms 6492 KB ok
13 Correct 1 ms 6492 KB ok
14 Correct 1 ms 6492 KB ok
15 Correct 1 ms 6488 KB ok
16 Correct 1 ms 6492 KB ok
17 Correct 1 ms 10584 KB ok
18 Correct 1 ms 10588 KB ok
19 Correct 1 ms 10588 KB ok
20 Correct 2 ms 10588 KB ok
21 Correct 1 ms 10588 KB ok
22 Correct 1 ms 10588 KB ok
23 Correct 2 ms 10588 KB ok
24 Correct 1 ms 10588 KB ok
25 Correct 2 ms 10616 KB ok
26 Correct 1 ms 10588 KB ok
27 Correct 1 ms 10588 KB ok
28 Correct 2 ms 10588 KB ok
29 Correct 2 ms 10584 KB ok
30 Correct 4 ms 37468 KB ok
31 Correct 5 ms 37440 KB ok
32 Correct 4 ms 37468 KB ok
33 Correct 5 ms 37432 KB ok
34 Correct 5 ms 37468 KB ok
35 Correct 4 ms 37468 KB ok
36 Correct 5 ms 37468 KB ok
37 Correct 5 ms 37468 KB ok
38 Correct 5 ms 37464 KB ok
39 Correct 4 ms 37464 KB ok
40 Correct 4 ms 37468 KB ok
41 Correct 4 ms 37468 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB ok
2 Correct 1 ms 6488 KB ok
3 Correct 1 ms 6492 KB ok
4 Correct 2 ms 12636 KB ok
5 Correct 3 ms 14684 KB ok
6 Correct 1 ms 6488 KB ok
7 Correct 1 ms 6488 KB ok
8 Correct 1 ms 6492 KB ok
9 Correct 1 ms 6492 KB ok
10 Correct 1 ms 6488 KB ok
11 Correct 1 ms 6488 KB ok
12 Correct 1 ms 6492 KB ok
13 Correct 1 ms 6492 KB ok
14 Correct 1 ms 6492 KB ok
15 Correct 1 ms 6488 KB ok
16 Correct 1 ms 6492 KB ok
17 Correct 1 ms 10584 KB ok
18 Correct 1 ms 10588 KB ok
19 Correct 1 ms 10588 KB ok
20 Correct 2 ms 10588 KB ok
21 Correct 1 ms 10588 KB ok
22 Correct 1 ms 10588 KB ok
23 Correct 2 ms 10588 KB ok
24 Correct 1 ms 10588 KB ok
25 Correct 2 ms 10616 KB ok
26 Correct 1 ms 10588 KB ok
27 Correct 1 ms 10588 KB ok
28 Correct 2 ms 10588 KB ok
29 Correct 2 ms 10584 KB ok
30 Correct 4 ms 37468 KB ok
31 Correct 5 ms 37440 KB ok
32 Correct 4 ms 37468 KB ok
33 Correct 5 ms 37432 KB ok
34 Correct 5 ms 37468 KB ok
35 Correct 4 ms 37468 KB ok
36 Correct 5 ms 37468 KB ok
37 Correct 5 ms 37468 KB ok
38 Correct 5 ms 37464 KB ok
39 Correct 4 ms 37464 KB ok
40 Correct 4 ms 37468 KB ok
41 Correct 4 ms 37468 KB ok
42 Correct 400 ms 522320 KB ok
43 Correct 361 ms 522568 KB ok
44 Correct 933 ms 522580 KB ok
45 Correct 919 ms 522632 KB ok
46 Correct 468 ms 522672 KB ok
47 Correct 669 ms 522664 KB ok
48 Correct 347 ms 522876 KB ok
49 Correct 368 ms 522564 KB ok
50 Correct 2360 ms 522564 KB ok
51 Correct 334 ms 522876 KB ok
52 Correct 333 ms 523244 KB ok
53 Correct 307 ms 522804 KB ok
54 Correct 314 ms 522916 KB ok
55 Correct 315 ms 523092 KB ok
56 Correct 352 ms 522916 KB ok
57 Correct 407 ms 523092 KB ok
58 Correct 397 ms 523064 KB ok
59 Correct 384 ms 522836 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB ok
2 Correct 1 ms 6488 KB ok
3 Correct 1 ms 6492 KB ok
4 Correct 2 ms 12636 KB ok
5 Correct 3 ms 14684 KB ok
6 Correct 1 ms 4444 KB ok
7 Correct 1 ms 6492 KB ok
8 Correct 42 ms 111340 KB ok
9 Correct 513 ms 522064 KB ok
10 Partially correct 227 ms 31824 KB partial
11 Correct 1 ms 6488 KB ok
12 Correct 1 ms 6488 KB ok
13 Correct 1 ms 6492 KB ok
14 Correct 1 ms 6492 KB ok
15 Correct 1 ms 6488 KB ok
16 Correct 1 ms 6488 KB ok
17 Correct 1 ms 6492 KB ok
18 Correct 1 ms 6492 KB ok
19 Correct 1 ms 6492 KB ok
20 Correct 1 ms 6488 KB ok
21 Correct 1 ms 6492 KB ok
22 Correct 1 ms 10584 KB ok
23 Correct 1 ms 10588 KB ok
24 Correct 1 ms 10588 KB ok
25 Correct 2 ms 10588 KB ok
26 Correct 1 ms 10588 KB ok
27 Correct 1 ms 10588 KB ok
28 Correct 2 ms 10588 KB ok
29 Correct 1 ms 10588 KB ok
30 Correct 2 ms 10616 KB ok
31 Correct 1 ms 10588 KB ok
32 Correct 1 ms 10588 KB ok
33 Correct 2 ms 10588 KB ok
34 Correct 2 ms 10584 KB ok
35 Correct 4 ms 37468 KB ok
36 Correct 5 ms 37440 KB ok
37 Correct 4 ms 37468 KB ok
38 Correct 5 ms 37432 KB ok
39 Correct 5 ms 37468 KB ok
40 Correct 4 ms 37468 KB ok
41 Correct 5 ms 37468 KB ok
42 Correct 5 ms 37468 KB ok
43 Correct 5 ms 37464 KB ok
44 Correct 4 ms 37464 KB ok
45 Correct 4 ms 37468 KB ok
46 Correct 4 ms 37468 KB ok
47 Correct 400 ms 522320 KB ok
48 Correct 361 ms 522568 KB ok
49 Correct 933 ms 522580 KB ok
50 Correct 919 ms 522632 KB ok
51 Correct 468 ms 522672 KB ok
52 Correct 669 ms 522664 KB ok
53 Correct 347 ms 522876 KB ok
54 Correct 368 ms 522564 KB ok
55 Correct 2360 ms 522564 KB ok
56 Correct 334 ms 522876 KB ok
57 Correct 333 ms 523244 KB ok
58 Correct 307 ms 522804 KB ok
59 Correct 314 ms 522916 KB ok
60 Correct 315 ms 523092 KB ok
61 Correct 352 ms 522916 KB ok
62 Correct 407 ms 523092 KB ok
63 Correct 397 ms 523064 KB ok
64 Correct 384 ms 522836 KB ok
65 Partially correct 227 ms 39504 KB partial
66 Partially correct 235 ms 39636 KB partial
67 Partially correct 230 ms 39508 KB partial
68 Partially correct 361 ms 39572 KB partial
69 Partially correct 230 ms 39660 KB partial
70 Partially correct 227 ms 39552 KB partial
71 Partially correct 229 ms 39504 KB partial
72 Partially correct 230 ms 39464 KB partial
73 Incorrect 233 ms 39764 KB wrong
74 Halted 0 ms 0 KB -