oj.uz

Submission #1072604

# Submission time Handle Problem Language Result Execution time Memory
1072604 2024-08-23T23:35:50 Z HorizonWest Soccer Stadium (IOI23_soccer) C++17
77.5 / 100
 4059 ms 937640 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 1 ms 348 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 0 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 3 ms 2140 KB ok
8 Correct 74 ms 44748 KB ok
9 Correct 1820 ms 832684 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 0 ms 348 KB ok
8 Correct 0 ms 344 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 0 ms 344 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 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 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 1 ms 348 KB ok
13 Correct 0 ms 344 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 1 ms 348 KB ok
16 Correct 1 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 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 1 ms 348 KB ok
26 Correct 1 ms 344 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 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 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 0 ms 348 KB ok
11 Correct 0 ms 344 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 0 ms 344 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 1 ms 348 KB ok
18 Correct 1 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 1 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 1 ms 348 KB ok
28 Correct 1 ms 344 KB ok
29 Correct 1 ms 344 KB ok
30 Correct 1 ms 604 KB ok
31 Correct 1 ms 604 KB ok
32 Correct 1 ms 344 KB ok
33 Correct 1 ms 344 KB ok
34 Correct 1 ms 344 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 0 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 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 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 0 ms 348 KB ok
11 Correct 0 ms 344 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 0 ms 344 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 1 ms 348 KB ok
18 Correct 1 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 1 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 1 ms 348 KB ok
28 Correct 1 ms 344 KB ok
29 Correct 1 ms 344 KB ok
30 Correct 1 ms 604 KB ok
31 Correct 1 ms 604 KB ok
32 Correct 1 ms 344 KB ok
33 Correct 1 ms 344 KB ok
34 Correct 1 ms 344 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 0 ms 348 KB ok
41 Correct 1 ms 604 KB ok
42 Correct 276 ms 57976 KB ok
43 Correct 228 ms 55908 KB ok
44 Correct 321 ms 63800 KB ok
45 Correct 332 ms 64116 KB ok
46 Correct 305 ms 63868 KB ok
47 Correct 76 ms 45256 KB ok
48 Correct 109 ms 49352 KB ok
49 Correct 102 ms 47808 KB ok
50 Correct 186 ms 57208 KB ok
51 Correct 163 ms 54208 KB ok
52 Correct 76 ms 46180 KB ok
53 Correct 72 ms 44996 KB ok
54 Correct 89 ms 46024 KB ok
55 Correct 90 ms 47300 KB ok
56 Correct 78 ms 45252 KB ok
57 Correct 140 ms 54208 KB ok
58 Correct 126 ms 54300 KB ok
59 Correct 150 ms 54128 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 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 3 ms 2140 KB ok
9 Correct 74 ms 44748 KB ok
10 Correct 1820 ms 832684 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 0 ms 348 KB ok
16 Correct 0 ms 344 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 344 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 1 ms 348 KB ok
23 Correct 1 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 1 ms 348 KB ok
28 Correct 0 ms 348 KB ok
29 Correct 1 ms 348 KB ok
30 Correct 0 ms 348 KB ok
31 Correct 0 ms 348 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 604 KB ok
36 Correct 1 ms 604 KB ok
37 Correct 1 ms 344 KB ok
38 Correct 1 ms 344 KB ok
39 Correct 1 ms 344 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 0 ms 348 KB ok
46 Correct 1 ms 604 KB ok
47 Correct 276 ms 57976 KB ok
48 Correct 228 ms 55908 KB ok
49 Correct 321 ms 63800 KB ok
50 Correct 332 ms 64116 KB ok
51 Correct 305 ms 63868 KB ok
52 Correct 76 ms 45256 KB ok
53 Correct 109 ms 49352 KB ok
54 Correct 102 ms 47808 KB ok
55 Correct 186 ms 57208 KB ok
56 Correct 163 ms 54208 KB ok
57 Correct 76 ms 46180 KB ok
58 Correct 72 ms 44996 KB ok
59 Correct 89 ms 46024 KB ok
60 Correct 90 ms 47300 KB ok
61 Correct 78 ms 45252 KB ok
62 Correct 140 ms 54208 KB ok
63 Correct 126 ms 54300 KB ok
64 Correct 150 ms 54128 KB ok
65 Partially correct 4059 ms 937640 KB partial
66 Correct 3213 ms 882436 KB ok
67 Correct 1640 ms 850320 KB ok
68 Partially correct 3737 ms 932508 KB partial
69 Partially correct 3682 ms 933228 KB partial
70 Partially correct 3536 ms 934288 KB partial
71 Correct 3562 ms 932452 KB ok
72 Correct 1835 ms 840592 KB ok
73 Correct 2682 ms 887224 KB ok
74 Correct 2890 ms 911208 KB ok
75 Correct 2776 ms 886880 KB ok
76 Correct 2169 ms 930108 KB ok
77 Correct 2357 ms 930144 KB ok
78 Correct 2695 ms 933124 KB ok
79 Correct 1567 ms 841044 KB ok
80 Correct 1579 ms 841400 KB ok
81 Correct 1894 ms 851800 KB ok
82 Correct 2661 ms 877940 KB ok
83 Correct 2511 ms 870300 KB ok
84 Correct 1380 ms 841472 KB ok
85 Correct 1220 ms 835944 KB ok
86 Correct 1520 ms 851672 KB ok
87 Correct 1653 ms 851472 KB ok
88 Correct 1729 ms 844148 KB ok
89 Correct 1815 ms 834144 KB ok
90 Correct 1725 ms 834200 KB ok
91 Correct 1785 ms 836740 KB ok
92 Correct 1794 ms 843372 KB ok
93 Correct 1697 ms 851360 KB ok
94 Correct 1319 ms 835904 KB ok
95 Correct 1330 ms 833352 KB ok
96 Correct 1336 ms 832948 KB ok
97 Correct 1174 ms 833200 KB ok
98 Correct 1318 ms 832816 KB ok
99 Correct 3109 ms 934812 KB ok
100 Correct 2005 ms 932764 KB ok
101 Correct 2055 ms 932772 KB ok
102 Correct 2075 ms 932720 KB ok
103 Correct 1986 ms 932768 KB ok
104 Correct 2031 ms 932664 KB ok
105 Correct 1846 ms 933024 KB ok
106 Correct 1734 ms 932720 KB ok
107 Correct 1887 ms 932956 KB ok
108 Correct 3496 ms 928172 KB ok
109 Correct 3624 ms 933544 KB ok