oj.uz

답안 #1072558

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1072558 2024-08-23T21:58:48 Z HorizonWest 축구 경기장 (IOI23_soccer) C++17
70 / 100
 3284 ms 1106200 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 = 3e6;

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 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)); 

    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) 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)));

    map <vector<int>, int> dp; 

    auto F = [&](auto F, int i, int j, int a, int b, int c, int d) -> int 
    {   cnt++;
        vector <int> x = { i, j, a, b, c, d };
        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;
            }
        }

        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;
            }
        }

        return dp[x] = (dp[x] + mx);
    };      
    
    int ans = 0; 

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB ok

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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 3 ms 2140 KB ok
8 Correct 74 ms 41880 KB ok
9 Correct 1167 ms 784724 KB ok

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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 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 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 344 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 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 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 2 ms 348 KB ok
16 Correct 1 ms 348 KB ok
17 Correct 1 ms 348 KB ok
18 Correct 0 ms 344 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 344 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

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 344 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 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 348 KB ok
17 Correct 2 ms 348 KB ok
18 Correct 1 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 0 ms 348 KB ok
23 Correct 0 ms 344 KB ok
24 Correct 0 ms 344 KB ok
25 Correct 1 ms 348 KB ok
26 Correct 1 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 604 KB ok
33 Correct 1 ms 604 KB ok
34 Correct 1 ms 604 KB ok
35 Correct 1 ms 604 KB ok
36 Correct 1 ms 600 KB ok
37 Correct 1 ms 604 KB ok
38 Correct 1 ms 604 KB ok
39 Correct 1 ms 604 KB ok
40 Correct 1 ms 600 KB ok
41 Correct 1 ms 600 KB ok

Subtask #5
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 344 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 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 348 KB ok
17 Correct 2 ms 348 KB ok
18 Correct 1 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 0 ms 348 KB ok
23 Correct 0 ms 344 KB ok
24 Correct 0 ms 344 KB ok
25 Correct 1 ms 348 KB ok
26 Correct 1 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 604 KB ok
33 Correct 1 ms 604 KB ok
34 Correct 1 ms 604 KB ok
35 Correct 1 ms 604 KB ok
36 Correct 1 ms 600 KB ok
37 Correct 1 ms 604 KB ok
38 Correct 1 ms 604 KB ok
39 Correct 1 ms 604 KB ok
40 Correct 1 ms 600 KB ok
41 Correct 1 ms 600 KB ok
42 Correct 558 ms 81748 KB ok
43 Correct 472 ms 76988 KB ok
44 Correct 783 ms 87908 KB ok
45 Correct 699 ms 83684 KB ok
46 Correct 682 ms 86100 KB ok
47 Correct 85 ms 43344 KB ok
48 Correct 249 ms 64592 KB ok
49 Correct 252 ms 62652 KB ok
50 Correct 327 ms 82636 KB ok
51 Correct 322 ms 68180 KB ok
52 Correct 239 ms 69680 KB ok
53 Correct 216 ms 68692 KB ok
54 Correct 236 ms 69200 KB ok
55 Correct 238 ms 69716 KB ok
56 Correct 168 ms 60052 KB ok
57 Correct 276 ms 62288 KB ok
58 Correct 295 ms 63312 KB ok
59 Correct 307 ms 64848 KB ok

Subtask #6
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 344 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 3 ms 2140 KB ok
9 Correct 74 ms 41880 KB ok
10 Correct 1167 ms 784724 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 1 ms 344 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 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 2 ms 348 KB ok
23 Correct 1 ms 348 KB ok
24 Correct 1 ms 348 KB ok
25 Correct 0 ms 344 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 344 KB ok
30 Correct 1 ms 348 KB ok
31 Correct 1 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 604 KB ok
38 Correct 1 ms 604 KB ok
39 Correct 1 ms 604 KB ok
40 Correct 1 ms 604 KB ok
41 Correct 1 ms 600 KB ok
42 Correct 1 ms 604 KB ok
43 Correct 1 ms 604 KB ok
44 Correct 1 ms 604 KB ok
45 Correct 1 ms 600 KB ok
46 Correct 1 ms 600 KB ok
47 Correct 558 ms 81748 KB ok
48 Correct 472 ms 76988 KB ok
49 Correct 783 ms 87908 KB ok
50 Correct 699 ms 83684 KB ok
51 Correct 682 ms 86100 KB ok
52 Correct 85 ms 43344 KB ok
53 Correct 249 ms 64592 KB ok
54 Correct 252 ms 62652 KB ok
55 Correct 327 ms 82636 KB ok
56 Correct 322 ms 68180 KB ok
57 Correct 239 ms 69680 KB ok
58 Correct 216 ms 68692 KB ok
59 Correct 236 ms 69200 KB ok
60 Correct 238 ms 69716 KB ok
61 Correct 168 ms 60052 KB ok
62 Correct 276 ms 62288 KB ok
63 Correct 295 ms 63312 KB ok
64 Correct 307 ms 64848 KB ok
65 Partially correct 2804 ms 919940 KB partial
66 Correct 2724 ms 1059156 KB ok
67 Partially correct 2657 ms 1106200 KB partial
68 Correct 3284 ms 902736 KB ok
69 Partially correct 3267 ms 913232 KB partial
70 Partially correct 3157 ms 914096 KB partial
71 Correct 2724 ms 895436 KB ok
72 Correct 1472 ms 798000 KB ok
73 Incorrect 3211 ms 964776 KB wrong
74 Halted 0 ms 0 KB -