oj.uz

Submission #885892

# Submission time Handle Problem Language Result Execution time Memory
885892 2023-12-11T02:01:02 Z jay_jayjay Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 118332 KB 
// {{{1
extern "C" int __lsan_is_turned_off() { return 1; }
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

#include <algorithm>
#include <complex>
#include <iostream>
#include <numeric>
#include <array>
#include <vector>
#include <string>
#include <deque>
#include <queue>
#include <map>
#include <set>
using namespace std;

#define ll long long
#define inf 0x3f3f3f3f
#define infl 0x3f3f3f3f3f3f3f3fll

#include <assert.h>
#ifdef DEBUG
#define dprintf(args...) fprintf(stderr,args)
#endif
#ifndef DEBUG
#define dprintf(args...) 69
#endif
#define all(x) (x).begin(), (x).end()
// 1}}}

#define N 2000
#define LG 20
int n;
int F[N][N];
int C[N][N];
int D[N][N];

int dp[N][N],aux[N][N];
int st_l[LG][N];
int st_r[LG][N];
// in col, row

void build(int st[LG][N], int m) {
        for(int lg = 1; lg < LG; lg++)
                for(int i=0;i+(1<<lg)<=N;i++)
                        // st[lg][i] repr [i...i+(1<<lg))
                        if(m)st[lg][i] = max(st[lg-1][i],st[lg-1][i+(1<<(lg-1))]);
                        else st[lg][i] = min(st[lg-1][i],st[lg-1][i+(1<<(lg-1))]);
}

int query(int st[LG][N],int m, int l, int r) {
        r++;
        int lg = __lg(r-l);
        //printf("l=%d r=%d lg=%d 1<<lg=%d\n",l,r,lg,1<<lg);
        if(m) return max(st[lg][l],st[lg][r-(1<<lg)]);
        else  return min(st[lg][l],st[lg][r-(1<<lg)]);
}

int solve(int c) {
        // solves if column of highest is c
        for(int y=0;y<n;y++) {
                st_l[0][y] = lower_bound(C[y],C[y]+n,C[y][c])-C[y];
                if(C[y][st_l[0][y]]==0)st_l[0][y]--;
                st_r[0][y] = upper_bound(C[y],C[y]+n,C[y][c])-C[y];
                //printf("%d, %d ( : %d)\n",st_l[0][y],st_r[0][y],C[y][c]);
        }
        build(st_l,1);
        build(st_r,0);

#define extent(l, r) (query(st_r,0,l,r) - query(st_l,1,l,r) - 1)
#define ok(l,r) (query(st_r,0,l,r)>c && query(st_l,1,l,r)<c)
#define val(l,r) (ok(l,r)?extent(l,r) : 0)
        for(int i=0;i<n;i++) {
                for(int j=n-1;j>=i;j--) {
                        dp[i][j]=val(i,j);
                }
        }
        for(int i=0;i<n;i++) {
                for(int j=n-1;j>i;j--) {
                        // transition to i+1,j
                        // and i,j-1
                        // i+1, j
                        aux[i+1][j] = val(i+1,j);
                        dp[i+1][j] = max(dp[i+1][j], (j-i) * (aux[i+1][j]-aux[i][j]) + dp[i][j]);

                        aux[i][j-1] = val(i,j-1);
                        dp[i][j-1] = max(dp[i][j-1], (j-i) * (aux[i][j-1]-aux[i][j]) + dp[i][j]);
                }
        }
        //printf("\nc=%d\n",c);
        int mx=0;
        for(int i=0;i<n;i++)
                for(int j=n-1;j>=i;j--) {
                        mx = max(mx,dp[i][j]);
                        //printf("[%d, %d] = %d\n",i,j,dp[i][j]);
                }
        //printf("c=%d: mx=%d\n",c,mx);
        return mx;
}

int biggest_stadium(int _n, vector<vector<int>> _f) {
        n=_n;
        int tot = 0;
        for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                        F[i][j]=_f[i][j];
        for(int i=0;i<n;i++) {
                for(int j=0;j<n;j++) tot += F[i][j];
                for(int j=0;j<n;j++)
                        C[i][j]=F[i][j];
                for(int j=1;j<n;j++)
                        C[i][j]+=C[i][j-1];
        }
        for(int i=0;i<n;i++) {
                for(int j=0;j<n;j++)
                        D[j][i]=F[j][i];
                for(int j=1;j<n;j++)
                        D[j][i]+=D[j-1][i];
        }
        if(tot == 1) {
                for(int i=0;i<n;i++)
                        for(int j=0;j<n;j++)
                                if(F[i][j])
                                {
                                        int mn = min({
                                                        (i+1)*(n-j),
                                                        (i+1)*(j+1),
                                                        (n-i)*(j+1),
                                                        (n-i)*(n-j)
                                                        });
                                        return n*n-mn;
                                }
        }
        //for(int i=0;i<n;i++) {
                //for(int j=0;j<n;j++)
                        //printf("%d ",F[i][j]);
                //printf("\n");
        //}
        //printf("\n");
        //for(int i=0;i<n;i++) {
                //for(int j=0;j<n;j++)
                        //printf("%d ",C[i][j]);
                //printf("\n");
        //}

        int best=0;
        for(int i=0;i<n;i++)best=max(best,solve(i));
        return best;
}

//int main()
//{
        //int tt;
        //scanf("%d",&tt);
        //for(int ttn=0;ttn<tt;ttn++)
        //{
                //int n;
                //scanf("%d",&n);
                //vector f(n,vector<int>(n));
                //for(int i=0;i<n;i++) {
                        //for(int j=0;j<n;j++) {
                                //scanf(" %c",&f[i][j]);f[i][j]=f[i][j]=='1';
                        //}
                //}
                //printf("%d\n",biggest_stadium(n,f));
        //}
//}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.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 6492 KB ok
4 Correct 1 ms 6492 KB ok
5 Correct 1 ms 10588 KB ok
6 Correct 1 ms 6492 KB ok
7 Correct 2 ms 8540 KB ok
8 Correct 22 ms 21076 KB ok
9 Correct 298 ms 79396 KB ok

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 2 ms 10584 KB ok
4 Correct 2 ms 10584 KB ok
5 Correct 1 ms 10588 KB ok
6 Correct 2 ms 10684 KB ok
7 Correct 1 ms 10588 KB ok
8 Correct 1 ms 10588 KB ok
9 Correct 2 ms 10588 KB ok
10 Correct 1 ms 10588 KB ok
11 Correct 1 ms 10588 KB ok
12 Correct 1 ms 10588 KB ok
13 Correct 1 ms 10584 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB ok
2 Correct 1 ms 6488 KB ok
3 Correct 1 ms 6492 KB ok
4 Correct 2 ms 10584 KB ok
5 Correct 2 ms 10584 KB ok
6 Correct 1 ms 10588 KB ok
7 Correct 2 ms 10684 KB ok
8 Correct 1 ms 10588 KB ok
9 Correct 1 ms 10588 KB ok
10 Correct 2 ms 10588 KB ok
11 Correct 1 ms 10588 KB ok
12 Correct 1 ms 10588 KB ok
13 Correct 1 ms 10588 KB ok
14 Correct 1 ms 10584 KB ok
15 Correct 2 ms 10588 KB ok
16 Correct 2 ms 10588 KB ok
17 Correct 2 ms 10588 KB ok
18 Correct 2 ms 10588 KB ok
19 Correct 2 ms 10588 KB ok
20 Correct 2 ms 10588 KB ok
21 Correct 2 ms 10588 KB ok
22 Correct 2 ms 10588 KB ok
23 Correct 2 ms 10588 KB ok
24 Correct 1 ms 10588 KB ok
25 Correct 2 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 10584 KB ok
2 Correct 1 ms 6488 KB ok
3 Correct 1 ms 6492 KB ok
4 Correct 1 ms 6492 KB ok
5 Correct 1 ms 6492 KB ok
6 Correct 2 ms 10584 KB ok
7 Correct 2 ms 10584 KB ok
8 Correct 1 ms 10588 KB ok
9 Correct 2 ms 10684 KB ok
10 Correct 1 ms 10588 KB ok
11 Correct 1 ms 10588 KB ok
12 Correct 2 ms 10588 KB ok
13 Correct 1 ms 10588 KB ok
14 Correct 1 ms 10588 KB ok
15 Correct 1 ms 10588 KB ok
16 Correct 1 ms 10584 KB ok
17 Correct 2 ms 10588 KB ok
18 Correct 2 ms 10588 KB ok
19 Correct 2 ms 10588 KB ok
20 Correct 2 ms 10588 KB ok
21 Correct 2 ms 10588 KB ok
22 Correct 2 ms 10588 KB ok
23 Correct 2 ms 10588 KB ok
24 Correct 2 ms 10588 KB ok
25 Correct 2 ms 10588 KB ok
26 Correct 1 ms 10588 KB ok
27 Correct 2 ms 10588 KB ok
28 Correct 2 ms 10588 KB ok
29 Correct 2 ms 10584 KB ok
30 Correct 3 ms 12636 KB ok
31 Correct 3 ms 12636 KB ok
32 Correct 3 ms 12636 KB ok
33 Correct 4 ms 12636 KB ok
34 Correct 3 ms 13044 KB ok
35 Correct 3 ms 12632 KB ok
36 Correct 3 ms 13044 KB ok
37 Correct 3 ms 12636 KB ok
38 Correct 3 ms 12636 KB ok
39 Correct 4 ms 12636 KB ok
40 Correct 3 ms 12636 KB ok
41 Correct 3 ms 12636 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB ok
2 Correct 1 ms 6488 KB ok
3 Correct 1 ms 6492 KB ok
4 Correct 1 ms 6492 KB ok
5 Correct 1 ms 6492 KB ok
6 Correct 2 ms 10584 KB ok
7 Correct 2 ms 10584 KB ok
8 Correct 1 ms 10588 KB ok
9 Correct 2 ms 10684 KB ok
10 Correct 1 ms 10588 KB ok
11 Correct 1 ms 10588 KB ok
12 Correct 2 ms 10588 KB ok
13 Correct 1 ms 10588 KB ok
14 Correct 1 ms 10588 KB ok
15 Correct 1 ms 10588 KB ok
16 Correct 1 ms 10584 KB ok
17 Correct 2 ms 10588 KB ok
18 Correct 2 ms 10588 KB ok
19 Correct 2 ms 10588 KB ok
20 Correct 2 ms 10588 KB ok
21 Correct 2 ms 10588 KB ok
22 Correct 2 ms 10588 KB ok
23 Correct 2 ms 10588 KB ok
24 Correct 2 ms 10588 KB ok
25 Correct 2 ms 10588 KB ok
26 Correct 1 ms 10588 KB ok
27 Correct 2 ms 10588 KB ok
28 Correct 2 ms 10588 KB ok
29 Correct 2 ms 10584 KB ok
30 Correct 3 ms 12636 KB ok
31 Correct 3 ms 12636 KB ok
32 Correct 3 ms 12636 KB ok
33 Correct 4 ms 12636 KB ok
34 Correct 3 ms 13044 KB ok
35 Correct 3 ms 12632 KB ok
36 Correct 3 ms 13044 KB ok
37 Correct 3 ms 12636 KB ok
38 Correct 3 ms 12636 KB ok
39 Correct 4 ms 12636 KB ok
40 Correct 3 ms 12636 KB ok
41 Correct 3 ms 12636 KB ok
42 Correct 1089 ms 31228 KB ok
43 Correct 1083 ms 31228 KB ok
44 Correct 1113 ms 31236 KB ok
45 Correct 1101 ms 31224 KB ok
46 Correct 1079 ms 31232 KB ok
47 Correct 1097 ms 31232 KB ok
48 Correct 1108 ms 31228 KB ok
49 Correct 1100 ms 31232 KB ok
50 Correct 1077 ms 31236 KB ok
51 Correct 1086 ms 31228 KB ok
52 Correct 1113 ms 31228 KB ok
53 Correct 1090 ms 31316 KB ok
54 Correct 1075 ms 31312 KB ok
55 Correct 1076 ms 31320 KB ok
56 Correct 1082 ms 31320 KB ok
57 Correct 1094 ms 31236 KB ok
58 Correct 1098 ms 31068 KB ok
59 Correct 1100 ms 31232 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB ok
2 Correct 1 ms 6488 KB ok
3 Correct 1 ms 6492 KB ok
4 Correct 1 ms 6492 KB ok
5 Correct 1 ms 6492 KB ok
6 Correct 1 ms 10588 KB ok
7 Correct 1 ms 6492 KB ok
8 Correct 2 ms 8540 KB ok
9 Correct 22 ms 21076 KB ok
10 Correct 298 ms 79396 KB ok
11 Correct 2 ms 10584 KB ok
12 Correct 2 ms 10584 KB ok
13 Correct 1 ms 10588 KB ok
14 Correct 2 ms 10684 KB ok
15 Correct 1 ms 10588 KB ok
16 Correct 1 ms 10588 KB ok
17 Correct 2 ms 10588 KB ok
18 Correct 1 ms 10588 KB ok
19 Correct 1 ms 10588 KB ok
20 Correct 1 ms 10588 KB ok
21 Correct 1 ms 10584 KB ok
22 Correct 2 ms 10588 KB ok
23 Correct 2 ms 10588 KB ok
24 Correct 2 ms 10588 KB ok
25 Correct 2 ms 10588 KB ok
26 Correct 2 ms 10588 KB ok
27 Correct 2 ms 10588 KB ok
28 Correct 2 ms 10588 KB ok
29 Correct 2 ms 10588 KB ok
30 Correct 2 ms 10588 KB ok
31 Correct 1 ms 10588 KB ok
32 Correct 2 ms 10588 KB ok
33 Correct 2 ms 10588 KB ok
34 Correct 2 ms 10584 KB ok
35 Correct 3 ms 12636 KB ok
36 Correct 3 ms 12636 KB ok
37 Correct 3 ms 12636 KB ok
38 Correct 4 ms 12636 KB ok
39 Correct 3 ms 13044 KB ok
40 Correct 3 ms 12632 KB ok
41 Correct 3 ms 13044 KB ok
42 Correct 3 ms 12636 KB ok
43 Correct 3 ms 12636 KB ok
44 Correct 4 ms 12636 KB ok
45 Correct 3 ms 12636 KB ok
46 Correct 3 ms 12636 KB ok
47 Correct 1089 ms 31228 KB ok
48 Correct 1083 ms 31228 KB ok
49 Correct 1113 ms 31236 KB ok
50 Correct 1101 ms 31224 KB ok
51 Correct 1079 ms 31232 KB ok
52 Correct 1097 ms 31232 KB ok
53 Correct 1108 ms 31228 KB ok
54 Correct 1100 ms 31232 KB ok
55 Correct 1077 ms 31236 KB ok
56 Correct 1086 ms 31228 KB ok
57 Correct 1113 ms 31228 KB ok
58 Correct 1090 ms 31316 KB ok
59 Correct 1075 ms 31312 KB ok
60 Correct 1076 ms 31320 KB ok
61 Correct 1082 ms 31320 KB ok
62 Correct 1094 ms 31236 KB ok
63 Correct 1098 ms 31068 KB ok
64 Correct 1100 ms 31232 KB ok
65 Execution timed out 4528 ms 118332 KB Time limit exceeded
66 Halted 0 ms 0 KB -