oj.uz

Submission #1072601

# Submission time Handle Problem Language Result Execution time Memory
1072601 2024-08-23T23:08:38 Z HorizonWest Soccer Stadium (IOI23_soccer) C++17
77.5 / 100
 4381 ms 941476 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 344 KB ok

Subtask #1
6.0 / 6.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 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 3 ms 2140 KB ok
8 Correct 72 ms 44896 KB ok
9 Correct 1516 ms 833208 KB ok

Subtask #2
8.0 / 8.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 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 344 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 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 0 ms 344 KB ok
2 Correct 1 ms 348 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 0 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 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 1 ms 348 KB ok
14 Correct 0 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 0 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 1 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 0 ms 348 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 1 ms 348 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 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 344 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 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 1 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 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 1 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 0 ms 348 KB ok
29 Correct 0 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 0 ms 348 KB ok
34 Correct 0 ms 348 KB ok
35 Correct 1 ms 344 KB ok
36 Correct 1 ms 344 KB ok
37 Correct 0 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 572 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 1 ms 348 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 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 344 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 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 1 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 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 1 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 0 ms 348 KB ok
29 Correct 0 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 0 ms 348 KB ok
34 Correct 0 ms 348 KB ok
35 Correct 1 ms 344 KB ok
36 Correct 1 ms 344 KB ok
37 Correct 0 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 572 KB ok
42 Correct 235 ms 57860 KB ok
43 Correct 217 ms 55956 KB ok
44 Correct 269 ms 63956 KB ok
45 Correct 259 ms 63860 KB ok
46 Correct 287 ms 63860 KB ok
47 Correct 90 ms 45256 KB ok
48 Correct 100 ms 49348 KB ok
49 Correct 95 ms 47652 KB ok
50 Correct 175 ms 57204 KB ok
51 Correct 147 ms 54208 KB ok
52 Correct 72 ms 46280 KB ok
53 Correct 65 ms 45000 KB ok
54 Correct 75 ms 45892 KB ok
55 Correct 88 ms 47304 KB ok
56 Correct 77 ms 45252 KB ok
57 Correct 123 ms 54056 KB ok
58 Correct 133 ms 54296 KB ok
59 Correct 128 ms 54212 KB ok

Subtask #6
7.5 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 1 ms 348 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 0 ms 348 KB ok
8 Correct 3 ms 2140 KB ok
9 Correct 72 ms 44896 KB ok
10 Correct 1516 ms 833208 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 344 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 348 KB ok
20 Correct 1 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 1 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 0 ms 348 KB ok
31 Correct 0 ms 348 KB ok
32 Correct 0 ms 348 KB ok
33 Correct 0 ms 348 KB ok
34 Correct 0 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 0 ms 348 KB ok
39 Correct 0 ms 348 KB ok
40 Correct 1 ms 344 KB ok
41 Correct 1 ms 344 KB ok
42 Correct 0 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 572 KB ok
47 Correct 235 ms 57860 KB ok
48 Correct 217 ms 55956 KB ok
49 Correct 269 ms 63956 KB ok
50 Correct 259 ms 63860 KB ok
51 Correct 287 ms 63860 KB ok
52 Correct 90 ms 45256 KB ok
53 Correct 100 ms 49348 KB ok
54 Correct 95 ms 47652 KB ok
55 Correct 175 ms 57204 KB ok
56 Correct 147 ms 54208 KB ok
57 Correct 72 ms 46280 KB ok
58 Correct 65 ms 45000 KB ok
59 Correct 75 ms 45892 KB ok
60 Correct 88 ms 47304 KB ok
61 Correct 77 ms 45252 KB ok
62 Correct 123 ms 54056 KB ok
63 Correct 133 ms 54296 KB ok
64 Correct 128 ms 54212 KB ok
65 Correct 3751 ms 937632 KB ok
66 Correct 2978 ms 883444 KB ok
67 Correct 1635 ms 850284 KB ok
68 Correct 3505 ms 933428 KB ok
69 Partially correct 3837 ms 934540 KB partial
70 Correct 3714 ms 939040 KB ok
71 Correct 3692 ms 936824 KB ok
72 Correct 2036 ms 846000 KB ok
73 Correct 2873 ms 895900 KB ok
74 Correct 3042 ms 919024 KB ok
75 Correct 2688 ms 895572 KB ok
76 Correct 2170 ms 938220 KB ok
77 Correct 2379 ms 938912 KB ok
78 Correct 2847 ms 940436 KB ok
79 Correct 1639 ms 848516 KB ok
80 Correct 1542 ms 848564 KB ok
81 Correct 1946 ms 859236 KB ok
82 Correct 2714 ms 885224 KB ok
83 Correct 2442 ms 877664 KB ok
84 Correct 1446 ms 850356 KB ok
85 Correct 1383 ms 843164 KB ok
86 Correct 1607 ms 859052 KB ok
87 Correct 1689 ms 858000 KB ok
88 Correct 1805 ms 851156 KB ok
89 Correct 1679 ms 840792 KB ok
90 Correct 1837 ms 842144 KB ok
91 Correct 1799 ms 843956 KB ok
92 Correct 1690 ms 851104 KB ok
93 Correct 1808 ms 857808 KB ok
94 Correct 1473 ms 843168 KB ok
95 Correct 1361 ms 840700 KB ok
96 Correct 1210 ms 841500 KB ok
97 Correct 1372 ms 841892 KB ok
98 Correct 1294 ms 841032 KB ok
99 Correct 3546 ms 935348 KB ok
100 Correct 2001 ms 941336 KB ok
101 Correct 2138 ms 940704 KB ok
102 Correct 1988 ms 941376 KB ok
103 Correct 2044 ms 941168 KB ok
104 Correct 2111 ms 941476 KB ok
105 Correct 2098 ms 940608 KB ok
106 Correct 1986 ms 941064 KB ok
107 Partially correct 1965 ms 941012 KB partial
108 Correct 4294 ms 935328 KB ok
109 Correct 4381 ms 940304 KB ok