oj.uz

Submission #1072596

# Submission time Handle Problem Language Result Execution time Memory
1072596 2024-08-23T22:58:36 Z HorizonWest Soccer Stadium (IOI23_soccer) C++17
77.5 / 100
 2875 ms 930552 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 = 4e6;

#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()
{
  	int ans = rand(); 
  	return (ans ^ (ans << 5) ^ (ans << 15));
}

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--){
            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]));
    }

    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 = rand() % 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 1 ms 348 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 1 ms 344 KB ok
6 Correct 1 ms 344 KB ok
7 Correct 3 ms 2396 KB ok
8 Correct 79 ms 45376 KB ok
9 Correct 1788 ms 840380 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 344 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 1 ms 348 KB ok
12 Correct 1 ms 348 KB ok
13 Correct 0 ms 348 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 1 ms 344 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 1 ms 348 KB ok
13 Correct 1 ms 348 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 1 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 344 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 440 KB ok
26 Correct 0 ms 348 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 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 1 ms 344 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 1 ms 348 KB ok
15 Correct 1 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 1 ms 348 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 344 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 440 KB ok
28 Correct 0 ms 348 KB ok
29 Correct 1 ms 348 KB ok
30 Correct 1 ms 604 KB ok
31 Correct 1 ms 604 KB ok
32 Correct 1 ms 348 KB ok
33 Correct 1 ms 344 KB ok
34 Correct 1 ms 344 KB ok
35 Correct 1 ms 344 KB ok
36 Correct 0 ms 348 KB ok
37 Correct 0 ms 348 KB ok
38 Correct 0 ms 348 KB ok
39 Correct 1 ms 348 KB ok
40 Correct 1 ms 348 KB ok
41 Correct 1 ms 604 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 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 1 ms 344 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 1 ms 348 KB ok
15 Correct 1 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 1 ms 348 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 344 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 440 KB ok
28 Correct 0 ms 348 KB ok
29 Correct 1 ms 348 KB ok
30 Correct 1 ms 604 KB ok
31 Correct 1 ms 604 KB ok
32 Correct 1 ms 348 KB ok
33 Correct 1 ms 344 KB ok
34 Correct 1 ms 344 KB ok
35 Correct 1 ms 344 KB ok
36 Correct 0 ms 348 KB ok
37 Correct 0 ms 348 KB ok
38 Correct 0 ms 348 KB ok
39 Correct 1 ms 348 KB ok
40 Correct 1 ms 348 KB ok
41 Correct 1 ms 604 KB ok
42 Correct 245 ms 58568 KB ok
43 Correct 197 ms 56448 KB ok
44 Correct 268 ms 64372 KB ok
45 Correct 246 ms 64344 KB ok
46 Correct 256 ms 64332 KB ok
47 Correct 82 ms 45768 KB ok
48 Correct 94 ms 49788 KB ok
49 Correct 92 ms 48320 KB ok
50 Correct 168 ms 57636 KB ok
51 Correct 140 ms 54716 KB ok
52 Correct 70 ms 46532 KB ok
53 Correct 59 ms 45512 KB ok
54 Correct 71 ms 46536 KB ok
55 Correct 81 ms 47560 KB ok
56 Correct 71 ms 45764 KB ok
57 Correct 122 ms 54720 KB ok
58 Correct 115 ms 54724 KB ok
59 Correct 134 ms 54756 KB ok

Subtask #6
7.5 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 344 KB ok
7 Correct 1 ms 344 KB ok
8 Correct 3 ms 2396 KB ok
9 Correct 79 ms 45376 KB ok
10 Correct 1788 ms 840380 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 1 ms 344 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 1 ms 348 KB ok
20 Correct 1 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 1 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 0 ms 344 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 440 KB ok
33 Correct 0 ms 348 KB ok
34 Correct 1 ms 348 KB ok
35 Correct 1 ms 604 KB ok
36 Correct 1 ms 604 KB ok
37 Correct 1 ms 348 KB ok
38 Correct 1 ms 344 KB ok
39 Correct 1 ms 344 KB ok
40 Correct 1 ms 344 KB ok
41 Correct 0 ms 348 KB ok
42 Correct 0 ms 348 KB ok
43 Correct 0 ms 348 KB ok
44 Correct 1 ms 348 KB ok
45 Correct 1 ms 348 KB ok
46 Correct 1 ms 604 KB ok
47 Correct 245 ms 58568 KB ok
48 Correct 197 ms 56448 KB ok
49 Correct 268 ms 64372 KB ok
50 Correct 246 ms 64344 KB ok
51 Correct 256 ms 64332 KB ok
52 Correct 82 ms 45768 KB ok
53 Correct 94 ms 49788 KB ok
54 Correct 92 ms 48320 KB ok
55 Correct 168 ms 57636 KB ok
56 Correct 140 ms 54716 KB ok
57 Correct 70 ms 46532 KB ok
58 Correct 59 ms 45512 KB ok
59 Correct 71 ms 46536 KB ok
60 Correct 81 ms 47560 KB ok
61 Correct 71 ms 45764 KB ok
62 Correct 122 ms 54720 KB ok
63 Correct 115 ms 54724 KB ok
64 Correct 134 ms 54756 KB ok
65 Correct 2676 ms 930552 KB ok
66 Correct 2370 ms 890296 KB ok
67 Correct 1324 ms 857756 KB ok
68 Partially correct 2489 ms 924860 KB partial
69 Partially correct 2429 ms 925252 KB partial
70 Correct 2459 ms 927388 KB ok
71 Correct 2440 ms 924248 KB ok
72 Correct 1587 ms 849380 KB ok
73 Correct 2045 ms 895900 KB ok
74 Correct 2438 ms 918688 KB ok
75 Correct 2103 ms 895392 KB ok
76 Correct 1430 ms 923916 KB ok
77 Correct 1505 ms 923948 KB ok
78 Correct 2061 ms 924948 KB ok
79 Correct 1314 ms 849304 KB ok
80 Correct 1266 ms 849500 KB ok
81 Correct 1476 ms 860068 KB ok
82 Correct 2109 ms 885200 KB ok
83 Correct 2064 ms 878484 KB ok
84 Correct 1153 ms 849052 KB ok
85 Correct 1091 ms 844096 KB ok
86 Correct 1250 ms 857752 KB ok
87 Correct 1224 ms 858532 KB ok
88 Correct 1361 ms 851100 KB ok
89 Correct 1382 ms 841320 KB ok
90 Correct 1423 ms 841368 KB ok
91 Correct 1616 ms 844196 KB ok
92 Correct 1440 ms 851764 KB ok
93 Correct 1478 ms 857848 KB ok
94 Correct 1084 ms 842884 KB ok
95 Correct 1061 ms 841808 KB ok
96 Correct 1064 ms 841592 KB ok
97 Correct 1047 ms 840984 KB ok
98 Correct 1038 ms 841396 KB ok
99 Correct 2198 ms 920420 KB ok
100 Correct 1473 ms 917148 KB ok
101 Correct 1526 ms 917044 KB ok
102 Correct 1518 ms 917916 KB ok
103 Correct 1464 ms 918432 KB ok
104 Correct 1454 ms 917152 KB ok
105 Correct 1479 ms 918428 KB ok
106 Correct 1453 ms 918160 KB ok
107 Correct 1426 ms 917052 KB ok
108 Correct 2875 ms 917404 KB ok
109 Correct 2741 ms 918056 KB ok