oj.uz

Submission #1072603

# Submission time Handle Problem Language Result Execution time Memory
1072603 2024-08-23T23:35:36 Z HorizonWest Soccer Stadium (IOI23_soccer) C++17
77.5 / 100
 4019 ms 940840 KB 
#include <iostream>
#include <complex>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <functional>
#include <bitset>
#include <queue>
#include <map>
#include <stack>
#include <cmath>
#include <cstdint>
#include <cassert>
using namespace std;

const int Max = 3001, Inf = 1e9, TLE = 5e6;

#define ll unsigned long long

int lg[Max], cnt; 

struct SPTMIN
{
    vector <vector <int>> spt; 

    int query(int i, int j){
        int x = lg[j-i+1];
        return min(spt[i][x], spt[j - (1LL << x) + 1][x]);
    }

    SPTMIN(vector <int> v)
    {
        int n = v.size();
        spt.assign(n + 1, vector <int> (lg[n] + 1, Inf));

        for(int j = 0; j < lg[n]+1; j++)
        {
            for(int i = 0; i < n; i++){
                if(j == 0){
                    spt[i][j] = v[i];
                    continue;
                }
                spt[i][j] = spt[i][j-1];
                if(i + (1LL << (j-1)) < n) spt[i][j] = min(spt[i][j-1], spt[i + (1LL << (j-1))][j-1]);
            }
        }
    }
};

struct SPTMAX
{
    vector <vector <int>> spt; 

    int query(int i, int j){
        int x = lg[j-i+1];
        return max(spt[i][x], spt[j - (1LL << x) + 1][x]);
    }

    SPTMAX(vector <int> v)
    {
        int n = v.size();
        spt.assign(n + 1, vector <int> (lg[n] + 1, 0));

        for(int j = 0; j < lg[n]+1; j++)
        {
            for(int i = 0; i < n; i++){
                if(j == 0){
                    spt[i][j] = v[i];
                    continue;
                }
                spt[i][j] = spt[i][j-1];
                if(i + (1LL << (j-1)) < n) spt[i][j] = max(spt[i][j-1], spt[i + (1LL << (j-1))][j-1]);
            }
        }
    }
};

int rnd(){
  	return abs(int(rand() ^ (rand() << 3LL) ^ (rand() << 6LL)));
}

int biggest_stadium(int n, std::vector<std::vector<int>> f)
{
    vector <vector<int>> A(n, vector <int> (n, 0)),
        B(n, vector <int> (n, 0)),
        C(n, vector <int> (n, 0)),
        D(n, vector <int> (n, 0)), 
        T(n, vector <int> (n, 0)); 

    vector <SPTMIN> sp1;
    vector <SPTMAX> sp2;

    cnt = 0;

    for(int i = 1; i <= n; i++){
        lg[i] = log2(i);
    }

    for(int i = 0; i < n; i++)
    {
        int last = -1; 
        for(int j = 0; j < n; j++){
            if(f[i][j] == 1) last = j; 
            A[i][j] = last;
        }   

        last = n;
        for(int j = n-1; j >= 0; j--){
            T[i][j] = last;
            if(f[i][j] == 1) {      
                if(j != n-1 && last == j+1){
                    T[i][j] = T[i][j+1];
                }else T[i][j] = j;
                last = j;
            } 
            B[i][j] = last;
        }     
    }

    for(int i = 0; i < n; i++)
    {
        int last = -1; 
        for(int j = 0; j < n; j++){
            if(f[j][i] == 1) last = j; 
            C[j][i] = last+1;
        }   

        last = n;
        for(int j = n-1; j >= 0; j--){
            if(f[j][i] == 1) last = j; 
            D[j][i] = last-1;
        }     
    }

    for(int i = 0; i < n; i++)
    {
        sp1.push_back(SPTMIN(D[i]));
        sp2.push_back(SPTMAX(C[i]));
    }
    
    //return 0;

    //vector <vector<vector<int>>> dp1(n + 1, vector <vector<int>> 
    //    (n + 1, vector <int> (n + 1, -1)));

    //vector <vector<vector<int>>> dp2(n + 1, vector <vector<int>> 
    //    (n + 1, vector <int> (n + 1, -1)));

    unordered_map <ll, int> dp; 

    auto F = [&](auto F, int i, int j, int a, int b, int c, int d) -> int 
    {   cnt++;

        long long x = ((ll) b) + (((ll) c) << 11LL) + (((ll) d) << 22LL) + (((ll) j) << 33LL) 
                               + (((ll) i) << 44LL) + (((ll) a) << 55LL);
        
        if(dp[x] != 0) return dp[x];
        dp[x] = (b - a + 1); 
        if(i != j) dp[x] += (d - c + 1);

        int mx = 0;

        if(i != 0)
        {
            for(int k = a; k <= b; k++) if(f[i-1][k] == 0)
            {
                int l1 = max(A[i-1][k]+1, a), r1 = min(B[i-1][k]-1, b);
                int l2 = max(c, l1), r2 =  min(d, r1);

                int ni = sp2[i].query(l1, r1), d = abs(ni - i) - 1, t = (r1 - l1 + 1);

                mx = max(mx, F(F, ni, j, l1, r1, l2, r2) - (r2 - l2 + 1) + d * t);

                k = r1;
            } else k = T[i-1][k];
        }

        if(j != n-1)
        {
            for(int k = c; k <= d; k++) if(f[j+1][k] == 0)
            {
                int l2 = max(A[j+1][k]+1, c), r2 = min(B[j+1][k]-1, d);
                int l1 = max(a, l2), r1 =  min(b, r2);

                int nj = sp1[j].query(l2, r2), d = abs(nj - j) - 1, t = (r2 - l2 + 1);

                mx = max(mx, F(F, i, nj, l1, r1, l2, r2) - (r1 - l1 + 1) + d * t);

                k = r2;
            } else k = T[j+1][k];
        }

        return dp[x] = (dp[x] + mx);
    };      
    
    int ans = 0; 
  	
  	srand(time(NULL));
  	vector <pair<int, int>> fx; 
  
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            fx.push_back({ i, j });
        }
    }
  	
  	int mod = (int) fx.size(); 
 	for(int i = 0; i < (int) fx.size(); i++){
      int x = rnd() % mod;
      swap(fx[i], fx[x]);
    }
  
  	for(auto& u : fx)
    {
      int i = u.first, j = u.second; 
      
      if(f[i][j] == 1) continue; 
      
      int l = A[i][j]+1, r = B[i][j]-1;

      ans = max(ans, F(F, i, i, l, r, l, r));

      if(n > 500 && cnt > TLE) {
        return ans;
      }
    }

    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 1 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 436 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 344 KB ok
7 Correct 4 ms 2396 KB ok
8 Correct 74 ms 45412 KB ok
9 Correct 1571 ms 841268 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 1 ms 348 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 0 ms 372 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 440 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 1 ms 348 KB ok
13 Correct 1 ms 604 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 436 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 0 ms 344 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 0 ms 372 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 440 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 1 ms 348 KB ok
14 Correct 1 ms 604 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 440 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 1 ms 348 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 436 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 1 ms 436 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 0 ms 372 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 440 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 1 ms 348 KB ok
16 Correct 1 ms 604 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 440 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 1 ms 348 KB ok
29 Correct 0 ms 348 KB ok
30 Correct 1 ms 604 KB ok
31 Correct 1 ms 440 KB ok
32 Correct 1 ms 604 KB ok
33 Correct 1 ms 348 KB ok
34 Correct 1 ms 348 KB ok
35 Correct 1 ms 348 KB ok
36 Correct 1 ms 348 KB ok
37 Correct 1 ms 348 KB ok
38 Correct 1 ms 348 KB ok
39 Correct 1 ms 348 KB ok
40 Correct 1 ms 348 KB ok
41 Correct 1 ms 444 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 436 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 1 ms 436 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 0 ms 372 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 440 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 1 ms 348 KB ok
16 Correct 1 ms 604 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 440 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 1 ms 348 KB ok
29 Correct 0 ms 348 KB ok
30 Correct 1 ms 604 KB ok
31 Correct 1 ms 440 KB ok
32 Correct 1 ms 604 KB ok
33 Correct 1 ms 348 KB ok
34 Correct 1 ms 348 KB ok
35 Correct 1 ms 348 KB ok
36 Correct 1 ms 348 KB ok
37 Correct 1 ms 348 KB ok
38 Correct 1 ms 348 KB ok
39 Correct 1 ms 348 KB ok
40 Correct 1 ms 348 KB ok
41 Correct 1 ms 444 KB ok
42 Correct 256 ms 58536 KB ok
43 Correct 234 ms 56216 KB ok
44 Correct 280 ms 64376 KB ok
45 Correct 259 ms 64420 KB ok
46 Correct 263 ms 64376 KB ok
47 Correct 77 ms 45832 KB ok
48 Correct 105 ms 49856 KB ok
49 Correct 101 ms 48096 KB ok
50 Correct 185 ms 57452 KB ok
51 Correct 156 ms 54624 KB ok
52 Correct 77 ms 46592 KB ok
53 Correct 67 ms 45512 KB ok
54 Correct 76 ms 46536 KB ok
55 Correct 81 ms 47800 KB ok
56 Correct 78 ms 45824 KB ok
57 Correct 133 ms 54720 KB ok
58 Correct 127 ms 54724 KB ok
59 Correct 130 ms 54720 KB ok

Subtask #6
7.5 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 436 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 1 ms 436 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 344 KB ok
8 Correct 4 ms 2396 KB ok
9 Correct 74 ms 45412 KB ok
10 Correct 1571 ms 841268 KB ok
11 Correct 0 ms 344 KB ok
12 Correct 1 ms 348 KB ok
13 Correct 0 ms 372 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 440 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 1 ms 348 KB ok
21 Correct 1 ms 604 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 440 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 0 ms 348 KB ok
29 Correct 0 ms 348 KB ok
30 Correct 0 ms 348 KB ok
31 Correct 0 ms 348 KB ok
32 Correct 0 ms 348 KB ok
33 Correct 1 ms 348 KB ok
34 Correct 0 ms 348 KB ok
35 Correct 1 ms 604 KB ok
36 Correct 1 ms 440 KB ok
37 Correct 1 ms 604 KB ok
38 Correct 1 ms 348 KB ok
39 Correct 1 ms 348 KB ok
40 Correct 1 ms 348 KB ok
41 Correct 1 ms 348 KB ok
42 Correct 1 ms 348 KB ok
43 Correct 1 ms 348 KB ok
44 Correct 1 ms 348 KB ok
45 Correct 1 ms 348 KB ok
46 Correct 1 ms 444 KB ok
47 Correct 256 ms 58536 KB ok
48 Correct 234 ms 56216 KB ok
49 Correct 280 ms 64376 KB ok
50 Correct 259 ms 64420 KB ok
51 Correct 263 ms 64376 KB ok
52 Correct 77 ms 45832 KB ok
53 Correct 105 ms 49856 KB ok
54 Correct 101 ms 48096 KB ok
55 Correct 185 ms 57452 KB ok
56 Correct 156 ms 54624 KB ok
57 Correct 77 ms 46592 KB ok
58 Correct 67 ms 45512 KB ok
59 Correct 76 ms 46536 KB ok
60 Correct 81 ms 47800 KB ok
61 Correct 78 ms 45824 KB ok
62 Correct 133 ms 54720 KB ok
63 Correct 127 ms 54724 KB ok
64 Correct 130 ms 54720 KB ok
65 Correct 3671 ms 940840 KB ok
66 Correct 3087 ms 889304 KB ok
67 Correct 1695 ms 857272 KB ok
68 Partially correct 3659 ms 932680 KB partial
69 Correct 3712 ms 934036 KB ok
70 Correct 3658 ms 934132 KB ok
71 Correct 3887 ms 933624 KB ok
72 Correct 1947 ms 840560 KB ok
73 Correct 2849 ms 887032 KB ok
74 Correct 2975 ms 910840 KB ok
75 Correct 2791 ms 886688 KB ok
76 Correct 2041 ms 930160 KB ok
77 Correct 1991 ms 930152 KB ok
78 Correct 2600 ms 933160 KB ok
79 Correct 1402 ms 841632 KB ok
80 Correct 1550 ms 841236 KB ok
81 Correct 1837 ms 851872 KB ok
82 Correct 2634 ms 879468 KB ok
83 Correct 2571 ms 871256 KB ok
84 Correct 1338 ms 842304 KB ok
85 Correct 1331 ms 835944 KB ok
86 Correct 1499 ms 850788 KB ok
87 Correct 1531 ms 851752 KB ok
88 Correct 1724 ms 843928 KB ok
89 Correct 1679 ms 833376 KB ok
90 Correct 1728 ms 834236 KB ok
91 Correct 1861 ms 836564 KB ok
92 Correct 1554 ms 844576 KB ok
93 Correct 1760 ms 850508 KB ok
94 Correct 1428 ms 835836 KB ok
95 Correct 1472 ms 833380 KB ok
96 Correct 1383 ms 832688 KB ok
97 Correct 1389 ms 832944 KB ok
98 Correct 1292 ms 833664 KB ok
99 Correct 3143 ms 934552 KB ok
100 Correct 2085 ms 932716 KB ok
101 Correct 2037 ms 933956 KB ok
102 Correct 2029 ms 934044 KB ok
103 Correct 2055 ms 932752 KB ok
104 Correct 2009 ms 934304 KB ok
105 Correct 1991 ms 932892 KB ok
106 Correct 1894 ms 933400 KB ok
107 Correct 1858 ms 932760 KB ok
108 Correct 3875 ms 926876 KB ok
109 Correct 4019 ms 932464 KB ok