oj.uz

Submission #840988

# Submission time Handle Problem Language Result Execution time Memory
840988 2023-09-01T03:27:18 Z bachhoangxuan Soccer Stadium (IOI23_soccer) C++17
100 / 100
 1372 ms 284484 KB 
#include "soccer.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int maxn=2005;
const int maxl=10;
const int inf=1e9;

map<int,int> dp[maxn][maxn];

int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(i) F[i][j]+=F[i-1][j];
            if(j) F[i][j]+=F[i][j-1];
            if(i && j) F[i][j]-=F[i-1][j-1];
        }
    }
    auto rect = [&](int x,int y,int u,int v){
        int res=F[u][v];
        if(x) res-=F[x-1][v];
        if(y) res-=F[u][y-1];
        if(x && y) res+=F[x-1][y-1];
        return res;
    };
    auto range = [&](int x,int l,int r){
        int lx=x,rx=x-1;
        for(int i=maxl;i>=0;i--){
            if((lx-(1<<i))>=0 && !rect(lx-(1<<i),l,x,r)) lx-=(1<<i);
            if((rx+(1<<i))<N && !rect(x,l,rx+(1<<i),r)) rx+=(1<<i);
        }
        return make_pair(lx,rx);
    };
    function<int(int,int,int)> cal = [&](int x,int l,int r){
        if(dp[l][r].find(x)!=dp[l][r].end()) return dp[l][r][x];
        int res=0;
        auto [lx,rx]=range(x,l,r);
        if(x!=lx) return cal(lx,l,r);
        for(int lt=l,rt=l;rt<=r;lt++,rt=max(rt,lt)){
            auto check = [&](int R){
                return (lx>=1 && !rect(lx-1,lt,x,R)) || (rx+1<N && !rect(x,lt,rx+1,R));
            };
            if(!check(rt)) continue;
            for(int i=maxl;i>=0;i--) if(rt+(1<<i)<=r && check(rt+(1<<i))) rt+=(1<<i);
            auto [nl,nr]=range(x,lt,rt);
            res=max(res,cal(x,lt,rt)+(lx-nl+nr-rx)*(rt-lt+1));
            rt++;
        }
        //cout << l << ' ' << r << ' ' << x << ' ' << res << '\n';
        return dp[l][r][x]=res;
    };
    int ans=0;
    for(int i=0;i<N;i++){
        pii p=range(i,0,N-1);
        //cout << p.fi << ' ' << p.se << '\n';
        ans=max(ans,cal(i,0,N-1)+(p.se-p.fi+1)*N);
    }
    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 188984 KB ok
2 Correct 74 ms 189016 KB ok
3 Correct 74 ms 189024 KB ok
4 Correct 74 ms 189004 KB ok
5 Correct 87 ms 189084 KB ok
6 Correct 80 ms 189004 KB ok
7 Correct 77 ms 189056 KB ok
8 Correct 92 ms 190968 KB ok
9 Correct 347 ms 220448 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 188984 KB ok
2 Correct 74 ms 189016 KB ok
3 Correct 77 ms 189060 KB ok
4 Correct 76 ms 189080 KB ok
5 Correct 77 ms 189016 KB ok
6 Correct 76 ms 189020 KB ok
7 Correct 76 ms 189080 KB ok
8 Correct 76 ms 188968 KB ok
9 Correct 75 ms 188996 KB ok
10 Correct 76 ms 189052 KB ok
11 Correct 76 ms 189092 KB ok
12 Correct 76 ms 189004 KB ok
13 Correct 85 ms 188984 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 188984 KB ok
2 Correct 75 ms 188984 KB ok
3 Correct 74 ms 189016 KB ok
4 Correct 77 ms 189060 KB ok
5 Correct 76 ms 189080 KB ok
6 Correct 77 ms 189016 KB ok
7 Correct 76 ms 189020 KB ok
8 Correct 76 ms 189080 KB ok
9 Correct 76 ms 188968 KB ok
10 Correct 75 ms 188996 KB ok
11 Correct 76 ms 189052 KB ok
12 Correct 76 ms 189092 KB ok
13 Correct 76 ms 189004 KB ok
14 Correct 85 ms 188984 KB ok
15 Correct 83 ms 189000 KB ok
16 Correct 80 ms 189048 KB ok
17 Correct 78 ms 188964 KB ok
18 Correct 80 ms 189004 KB ok
19 Correct 80 ms 189136 KB ok
20 Correct 77 ms 188992 KB ok
21 Correct 80 ms 189000 KB ok
22 Correct 77 ms 189036 KB ok
23 Correct 74 ms 189012 KB ok
24 Correct 78 ms 189004 KB ok
25 Correct 77 ms 189004 KB ok
26 Correct 78 ms 189028 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 188984 KB ok
2 Correct 75 ms 188984 KB ok
3 Correct 74 ms 189016 KB ok
4 Correct 74 ms 189024 KB ok
5 Correct 74 ms 189004 KB ok
6 Correct 77 ms 189060 KB ok
7 Correct 76 ms 189080 KB ok
8 Correct 77 ms 189016 KB ok
9 Correct 76 ms 189020 KB ok
10 Correct 76 ms 189080 KB ok
11 Correct 76 ms 188968 KB ok
12 Correct 75 ms 188996 KB ok
13 Correct 76 ms 189052 KB ok
14 Correct 76 ms 189092 KB ok
15 Correct 76 ms 189004 KB ok
16 Correct 85 ms 188984 KB ok
17 Correct 83 ms 189000 KB ok
18 Correct 80 ms 189048 KB ok
19 Correct 78 ms 188964 KB ok
20 Correct 80 ms 189004 KB ok
21 Correct 80 ms 189136 KB ok
22 Correct 77 ms 188992 KB ok
23 Correct 80 ms 189000 KB ok
24 Correct 77 ms 189036 KB ok
25 Correct 74 ms 189012 KB ok
26 Correct 78 ms 189004 KB ok
27 Correct 77 ms 189004 KB ok
28 Correct 78 ms 189028 KB ok
29 Correct 77 ms 189036 KB ok
30 Correct 77 ms 188996 KB ok
31 Correct 84 ms 189020 KB ok
32 Correct 82 ms 189004 KB ok
33 Correct 76 ms 188992 KB ok
34 Correct 76 ms 189028 KB ok
35 Correct 83 ms 188976 KB ok
36 Correct 80 ms 189072 KB ok
37 Correct 76 ms 189096 KB ok
38 Correct 77 ms 189016 KB ok
39 Correct 85 ms 189056 KB ok
40 Correct 79 ms 189028 KB ok
41 Correct 83 ms 189032 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 188984 KB ok
2 Correct 75 ms 188984 KB ok
3 Correct 74 ms 189016 KB ok
4 Correct 74 ms 189024 KB ok
5 Correct 74 ms 189004 KB ok
6 Correct 77 ms 189060 KB ok
7 Correct 76 ms 189080 KB ok
8 Correct 77 ms 189016 KB ok
9 Correct 76 ms 189020 KB ok
10 Correct 76 ms 189080 KB ok
11 Correct 76 ms 188968 KB ok
12 Correct 75 ms 188996 KB ok
13 Correct 76 ms 189052 KB ok
14 Correct 76 ms 189092 KB ok
15 Correct 76 ms 189004 KB ok
16 Correct 85 ms 188984 KB ok
17 Correct 83 ms 189000 KB ok
18 Correct 80 ms 189048 KB ok
19 Correct 78 ms 188964 KB ok
20 Correct 80 ms 189004 KB ok
21 Correct 80 ms 189136 KB ok
22 Correct 77 ms 188992 KB ok
23 Correct 80 ms 189000 KB ok
24 Correct 77 ms 189036 KB ok
25 Correct 74 ms 189012 KB ok
26 Correct 78 ms 189004 KB ok
27 Correct 77 ms 189004 KB ok
28 Correct 78 ms 189028 KB ok
29 Correct 77 ms 189036 KB ok
30 Correct 77 ms 188996 KB ok
31 Correct 84 ms 189020 KB ok
32 Correct 82 ms 189004 KB ok
33 Correct 76 ms 188992 KB ok
34 Correct 76 ms 189028 KB ok
35 Correct 83 ms 188976 KB ok
36 Correct 80 ms 189072 KB ok
37 Correct 76 ms 189096 KB ok
38 Correct 77 ms 189016 KB ok
39 Correct 85 ms 189056 KB ok
40 Correct 79 ms 189028 KB ok
41 Correct 83 ms 189032 KB ok
42 Correct 129 ms 193376 KB ok
43 Correct 134 ms 194036 KB ok
44 Correct 108 ms 191692 KB ok
45 Correct 101 ms 191440 KB ok
46 Correct 124 ms 192720 KB ok
47 Correct 94 ms 191056 KB ok
48 Correct 101 ms 191104 KB ok
49 Correct 95 ms 191008 KB ok
50 Correct 106 ms 191108 KB ok
51 Correct 106 ms 191876 KB ok
52 Correct 97 ms 191040 KB ok
53 Correct 99 ms 191048 KB ok
54 Correct 105 ms 191108 KB ok
55 Correct 95 ms 191036 KB ok
56 Correct 96 ms 191052 KB ok
57 Correct 116 ms 194120 KB ok
58 Correct 122 ms 194544 KB ok
59 Correct 129 ms 194856 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 188984 KB ok
2 Correct 75 ms 188984 KB ok
3 Correct 74 ms 189016 KB ok
4 Correct 74 ms 189024 KB ok
5 Correct 74 ms 189004 KB ok
6 Correct 87 ms 189084 KB ok
7 Correct 80 ms 189004 KB ok
8 Correct 77 ms 189056 KB ok
9 Correct 92 ms 190968 KB ok
10 Correct 347 ms 220448 KB ok
11 Correct 77 ms 189060 KB ok
12 Correct 76 ms 189080 KB ok
13 Correct 77 ms 189016 KB ok
14 Correct 76 ms 189020 KB ok
15 Correct 76 ms 189080 KB ok
16 Correct 76 ms 188968 KB ok
17 Correct 75 ms 188996 KB ok
18 Correct 76 ms 189052 KB ok
19 Correct 76 ms 189092 KB ok
20 Correct 76 ms 189004 KB ok
21 Correct 85 ms 188984 KB ok
22 Correct 83 ms 189000 KB ok
23 Correct 80 ms 189048 KB ok
24 Correct 78 ms 188964 KB ok
25 Correct 80 ms 189004 KB ok
26 Correct 80 ms 189136 KB ok
27 Correct 77 ms 188992 KB ok
28 Correct 80 ms 189000 KB ok
29 Correct 77 ms 189036 KB ok
30 Correct 74 ms 189012 KB ok
31 Correct 78 ms 189004 KB ok
32 Correct 77 ms 189004 KB ok
33 Correct 78 ms 189028 KB ok
34 Correct 77 ms 189036 KB ok
35 Correct 77 ms 188996 KB ok
36 Correct 84 ms 189020 KB ok
37 Correct 82 ms 189004 KB ok
38 Correct 76 ms 188992 KB ok
39 Correct 76 ms 189028 KB ok
40 Correct 83 ms 188976 KB ok
41 Correct 80 ms 189072 KB ok
42 Correct 76 ms 189096 KB ok
43 Correct 77 ms 189016 KB ok
44 Correct 85 ms 189056 KB ok
45 Correct 79 ms 189028 KB ok
46 Correct 83 ms 189032 KB ok
47 Correct 129 ms 193376 KB ok
48 Correct 134 ms 194036 KB ok
49 Correct 108 ms 191692 KB ok
50 Correct 101 ms 191440 KB ok
51 Correct 124 ms 192720 KB ok
52 Correct 94 ms 191056 KB ok
53 Correct 101 ms 191104 KB ok
54 Correct 95 ms 191008 KB ok
55 Correct 106 ms 191108 KB ok
56 Correct 106 ms 191876 KB ok
57 Correct 97 ms 191040 KB ok
58 Correct 99 ms 191048 KB ok
59 Correct 105 ms 191108 KB ok
60 Correct 95 ms 191036 KB ok
61 Correct 96 ms 191052 KB ok
62 Correct 116 ms 194120 KB ok
63 Correct 122 ms 194544 KB ok
64 Correct 129 ms 194856 KB ok
65 Correct 1372 ms 258616 KB ok
66 Correct 1083 ms 256976 KB ok
67 Correct 600 ms 237240 KB ok
68 Correct 422 ms 223452 KB ok
69 Correct 615 ms 232188 KB ok
70 Correct 769 ms 239416 KB ok
71 Correct 391 ms 222680 KB ok
72 Correct 347 ms 221688 KB ok
73 Correct 372 ms 221592 KB ok
74 Correct 371 ms 221728 KB ok
75 Correct 378 ms 221716 KB ok
76 Correct 617 ms 221664 KB ok
77 Correct 640 ms 221724 KB ok
78 Correct 482 ms 229272 KB ok
79 Correct 440 ms 224856 KB ok
80 Correct 444 ms 223772 KB ok
81 Correct 415 ms 223880 KB ok
82 Correct 454 ms 226724 KB ok
83 Correct 661 ms 235828 KB ok
84 Correct 369 ms 221724 KB ok
85 Correct 391 ms 221592 KB ok
86 Correct 370 ms 221816 KB ok
87 Correct 373 ms 222360 KB ok
88 Correct 372 ms 221656 KB ok
89 Correct 361 ms 221644 KB ok
90 Correct 381 ms 221724 KB ok
91 Correct 378 ms 221640 KB ok
92 Correct 512 ms 230424 KB ok
93 Correct 545 ms 231988 KB ok
94 Correct 434 ms 224992 KB ok
95 Correct 403 ms 223228 KB ok
96 Correct 395 ms 222900 KB ok
97 Correct 398 ms 222628 KB ok
98 Correct 386 ms 222240 KB ok
99 Correct 1010 ms 270676 KB ok
100 Correct 795 ms 268992 KB ok
101 Correct 779 ms 264384 KB ok
102 Correct 812 ms 268976 KB ok
103 Correct 888 ms 276920 KB ok
104 Correct 918 ms 279840 KB ok
105 Correct 940 ms 282084 KB ok
106 Correct 974 ms 284484 KB ok
107 Correct 946 ms 284072 KB ok
108 Correct 511 ms 225520 KB ok
109 Correct 564 ms 225452 KB ok