oj.uz

Submission #928404

# Submission time Handle Problem Language Result Execution time Memory
928404 2024-02-16T10:30:30 Z abcvuitunggio Soccer Stadium (IOI23_soccer) C++17
77.5 / 100
 3675 ms 1053652 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn=2006;
int n,ans,s[mxn][mxn];
vector <int> dp[mxn][mxn],l[mxn][mxn],r[mxn][mxn];
int biggest_stadium(int N, vector <vector <int>> F){
    n=N;
    int S=0;
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++){
            s[i+1][j]=s[i][j]+F[i][j];
            if (!F[i][j])
                S=j;
        }
    for (int k=(n>500)*S;k<=(n>500?S:n);k++)
        for (int i=0;i<=n;i++){
            int x=k,y=k;
            for (int j=n;j>=i;j--){
                while (x&&s[j][x-1]==s[i][x-1])
                    x--;
                l[i][j].push_back(x);
                while (y<n&&s[j][y]==s[i][y])
                    y++;
                r[i][j].push_back(y);
                dp[i][j].push_back(0);
            }
        }
    for (int L=1;L<=n;L++)
        for (int i=0;i+L<=n;i++)
            for (int k=0;k<=(n<=500)*n;k++){
                int j=i+L;
                dp[i][j][k]=max(dp[i+1][j][k],dp[i][j-1][k])+r[i][j][k]-l[i][j][k];
            }
    for (int i=0;i<=(n<=500)*n;i++)
        ans=max(ans,dp[0][n][i]);
    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 285784 KB ok
2 Correct 62 ms 285768 KB ok
3 Correct 64 ms 285748 KB ok
4 Correct 61 ms 285776 KB ok
5 Correct 61 ms 285640 KB ok
6 Correct 62 ms 285580 KB ok
7 Correct 80 ms 293816 KB ok
8 Correct 3514 ms 1053388 KB ok
9 Correct 634 ms 519156 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 285784 KB ok
2 Correct 62 ms 285768 KB ok
3 Correct 61 ms 285780 KB ok
4 Correct 62 ms 285568 KB ok
5 Correct 61 ms 285776 KB ok
6 Correct 67 ms 285700 KB ok
7 Correct 61 ms 285736 KB ok
8 Correct 61 ms 285776 KB ok
9 Correct 62 ms 285780 KB ok
10 Correct 62 ms 285776 KB ok
11 Correct 62 ms 285780 KB ok
12 Correct 63 ms 285776 KB ok
13 Correct 64 ms 285840 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 285748 KB ok
2 Correct 62 ms 285784 KB ok
3 Correct 62 ms 285768 KB ok
4 Correct 61 ms 285780 KB ok
5 Correct 62 ms 285568 KB ok
6 Correct 61 ms 285776 KB ok
7 Correct 67 ms 285700 KB ok
8 Correct 61 ms 285736 KB ok
9 Correct 61 ms 285776 KB ok
10 Correct 62 ms 285780 KB ok
11 Correct 62 ms 285776 KB ok
12 Correct 62 ms 285780 KB ok
13 Correct 63 ms 285776 KB ok
14 Correct 64 ms 285840 KB ok
15 Correct 61 ms 285776 KB ok
16 Correct 63 ms 285780 KB ok
17 Correct 61 ms 285788 KB ok
18 Correct 62 ms 285780 KB ok
19 Correct 65 ms 285776 KB ok
20 Correct 65 ms 285768 KB ok
21 Correct 66 ms 285784 KB ok
22 Correct 62 ms 285788 KB ok
23 Correct 62 ms 285712 KB ok
24 Correct 63 ms 285776 KB ok
25 Correct 61 ms 285776 KB ok
26 Correct 66 ms 285768 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 285748 KB ok
2 Correct 62 ms 285784 KB ok
3 Correct 62 ms 285768 KB ok
4 Correct 64 ms 285748 KB ok
5 Correct 61 ms 285776 KB ok
6 Correct 61 ms 285780 KB ok
7 Correct 62 ms 285568 KB ok
8 Correct 61 ms 285776 KB ok
9 Correct 67 ms 285700 KB ok
10 Correct 61 ms 285736 KB ok
11 Correct 61 ms 285776 KB ok
12 Correct 62 ms 285780 KB ok
13 Correct 62 ms 285776 KB ok
14 Correct 62 ms 285780 KB ok
15 Correct 63 ms 285776 KB ok
16 Correct 64 ms 285840 KB ok
17 Correct 61 ms 285776 KB ok
18 Correct 63 ms 285780 KB ok
19 Correct 61 ms 285788 KB ok
20 Correct 62 ms 285780 KB ok
21 Correct 65 ms 285776 KB ok
22 Correct 65 ms 285768 KB ok
23 Correct 66 ms 285784 KB ok
24 Correct 62 ms 285788 KB ok
25 Correct 62 ms 285712 KB ok
26 Correct 63 ms 285776 KB ok
27 Correct 61 ms 285776 KB ok
28 Correct 66 ms 285768 KB ok
29 Correct 62 ms 285664 KB ok
30 Correct 64 ms 286036 KB ok
31 Correct 63 ms 286032 KB ok
32 Correct 62 ms 286032 KB ok
33 Correct 63 ms 285948 KB ok
34 Correct 63 ms 286032 KB ok
35 Correct 63 ms 286036 KB ok
36 Correct 63 ms 285944 KB ok
37 Correct 63 ms 285932 KB ok
38 Correct 63 ms 286068 KB ok
39 Correct 62 ms 286036 KB ok
40 Correct 62 ms 285932 KB ok
41 Correct 62 ms 285880 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 285748 KB ok
2 Correct 62 ms 285784 KB ok
3 Correct 62 ms 285768 KB ok
4 Correct 64 ms 285748 KB ok
5 Correct 61 ms 285776 KB ok
6 Correct 61 ms 285780 KB ok
7 Correct 62 ms 285568 KB ok
8 Correct 61 ms 285776 KB ok
9 Correct 67 ms 285700 KB ok
10 Correct 61 ms 285736 KB ok
11 Correct 61 ms 285776 KB ok
12 Correct 62 ms 285780 KB ok
13 Correct 62 ms 285776 KB ok
14 Correct 62 ms 285780 KB ok
15 Correct 63 ms 285776 KB ok
16 Correct 64 ms 285840 KB ok
17 Correct 61 ms 285776 KB ok
18 Correct 63 ms 285780 KB ok
19 Correct 61 ms 285788 KB ok
20 Correct 62 ms 285780 KB ok
21 Correct 65 ms 285776 KB ok
22 Correct 65 ms 285768 KB ok
23 Correct 66 ms 285784 KB ok
24 Correct 62 ms 285788 KB ok
25 Correct 62 ms 285712 KB ok
26 Correct 63 ms 285776 KB ok
27 Correct 61 ms 285776 KB ok
28 Correct 66 ms 285768 KB ok
29 Correct 62 ms 285664 KB ok
30 Correct 64 ms 286036 KB ok
31 Correct 63 ms 286032 KB ok
32 Correct 62 ms 286032 KB ok
33 Correct 63 ms 285948 KB ok
34 Correct 63 ms 286032 KB ok
35 Correct 63 ms 286036 KB ok
36 Correct 63 ms 285944 KB ok
37 Correct 63 ms 285932 KB ok
38 Correct 63 ms 286068 KB ok
39 Correct 62 ms 286036 KB ok
40 Correct 62 ms 285932 KB ok
41 Correct 62 ms 285880 KB ok
42 Correct 3367 ms 1053332 KB ok
43 Correct 3540 ms 1053468 KB ok
44 Correct 3383 ms 1053176 KB ok
45 Correct 3386 ms 1053156 KB ok
46 Correct 3360 ms 1053328 KB ok
47 Correct 3393 ms 1053280 KB ok
48 Correct 3340 ms 1053332 KB ok
49 Correct 3358 ms 1053264 KB ok
50 Correct 3365 ms 1053452 KB ok
51 Correct 3399 ms 1053460 KB ok
52 Correct 3443 ms 1053588 KB ok
53 Correct 3420 ms 1053272 KB ok
54 Correct 3390 ms 1053272 KB ok
55 Correct 3387 ms 1053268 KB ok
56 Correct 3357 ms 1053328 KB ok
57 Correct 3673 ms 1053328 KB ok
58 Correct 3675 ms 1053652 KB ok
59 Correct 3433 ms 1053324 KB ok

Subtask #6
7.5 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 285748 KB ok
2 Correct 62 ms 285784 KB ok
3 Correct 62 ms 285768 KB ok
4 Correct 64 ms 285748 KB ok
5 Correct 61 ms 285776 KB ok
6 Correct 61 ms 285640 KB ok
7 Correct 62 ms 285580 KB ok
8 Correct 80 ms 293816 KB ok
9 Correct 3514 ms 1053388 KB ok
10 Correct 634 ms 519156 KB ok
11 Correct 61 ms 285780 KB ok
12 Correct 62 ms 285568 KB ok
13 Correct 61 ms 285776 KB ok
14 Correct 67 ms 285700 KB ok
15 Correct 61 ms 285736 KB ok
16 Correct 61 ms 285776 KB ok
17 Correct 62 ms 285780 KB ok
18 Correct 62 ms 285776 KB ok
19 Correct 62 ms 285780 KB ok
20 Correct 63 ms 285776 KB ok
21 Correct 64 ms 285840 KB ok
22 Correct 61 ms 285776 KB ok
23 Correct 63 ms 285780 KB ok
24 Correct 61 ms 285788 KB ok
25 Correct 62 ms 285780 KB ok
26 Correct 65 ms 285776 KB ok
27 Correct 65 ms 285768 KB ok
28 Correct 66 ms 285784 KB ok
29 Correct 62 ms 285788 KB ok
30 Correct 62 ms 285712 KB ok
31 Correct 63 ms 285776 KB ok
32 Correct 61 ms 285776 KB ok
33 Correct 66 ms 285768 KB ok
34 Correct 62 ms 285664 KB ok
35 Correct 64 ms 286036 KB ok
36 Correct 63 ms 286032 KB ok
37 Correct 62 ms 286032 KB ok
38 Correct 63 ms 285948 KB ok
39 Correct 63 ms 286032 KB ok
40 Correct 63 ms 286036 KB ok
41 Correct 63 ms 285944 KB ok
42 Correct 63 ms 285932 KB ok
43 Correct 63 ms 286068 KB ok
44 Correct 62 ms 286036 KB ok
45 Correct 62 ms 285932 KB ok
46 Correct 62 ms 285880 KB ok
47 Correct 3367 ms 1053332 KB ok
48 Correct 3540 ms 1053468 KB ok
49 Correct 3383 ms 1053176 KB ok
50 Correct 3386 ms 1053156 KB ok
51 Correct 3360 ms 1053328 KB ok
52 Correct 3393 ms 1053280 KB ok
53 Correct 3340 ms 1053332 KB ok
54 Correct 3358 ms 1053264 KB ok
55 Correct 3365 ms 1053452 KB ok
56 Correct 3399 ms 1053460 KB ok
57 Correct 3443 ms 1053588 KB ok
58 Correct 3420 ms 1053272 KB ok
59 Correct 3390 ms 1053272 KB ok
60 Correct 3387 ms 1053268 KB ok
61 Correct 3357 ms 1053328 KB ok
62 Correct 3673 ms 1053328 KB ok
63 Correct 3675 ms 1053652 KB ok
64 Correct 3433 ms 1053324 KB ok
65 Partially correct 687 ms 519160 KB partial
66 Partially correct 649 ms 519256 KB partial
67 Partially correct 641 ms 519004 KB partial
68 Partially correct 631 ms 518996 KB partial
69 Partially correct 648 ms 519152 KB partial
70 Partially correct 659 ms 519216 KB partial
71 Partially correct 634 ms 519224 KB partial
72 Partially correct 646 ms 518996 KB partial
73 Correct 670 ms 519472 KB ok
74 Correct 662 ms 519484 KB ok
75 Correct 673 ms 519156 KB ok
76 Correct 635 ms 519160 KB ok
77 Partially correct 658 ms 519020 KB partial
78 Partially correct 651 ms 519360 KB partial
79 Partially correct 690 ms 518996 KB partial
80 Partially correct 638 ms 519164 KB partial
81 Partially correct 667 ms 519236 KB partial
82 Partially correct 643 ms 518992 KB partial
83 Partially correct 701 ms 519276 KB partial
84 Partially correct 690 ms 519596 KB partial
85 Partially correct 696 ms 519036 KB partial
86 Partially correct 698 ms 519232 KB partial
87 Correct 761 ms 519292 KB ok
88 Partially correct 672 ms 519132 KB partial
89 Partially correct 686 ms 519160 KB partial
90 Partially correct 650 ms 519200 KB partial
91 Partially correct 647 ms 519156 KB partial
92 Partially correct 685 ms 519252 KB partial
93 Partially correct 651 ms 519408 KB partial
94 Partially correct 653 ms 519228 KB partial
95 Partially correct 682 ms 519160 KB partial
96 Partially correct 639 ms 519156 KB partial
97 Partially correct 627 ms 519224 KB partial
98 Partially correct 640 ms 519080 KB partial
99 Correct 634 ms 519152 KB ok
100 Partially correct 634 ms 519220 KB partial
101 Partially correct 635 ms 518992 KB partial
102 Partially correct 647 ms 519160 KB partial
103 Partially correct 650 ms 518996 KB partial
104 Partially correct 724 ms 519092 KB partial
105 Partially correct 685 ms 519324 KB partial
106 Partially correct 747 ms 519408 KB partial
107 Correct 715 ms 519252 KB ok
108 Partially correct 735 ms 518996 KB partial
109 Correct 736 ms 519272 KB ok