oj.uz

Submission #843662

# Submission time Handle Problem Language Result Execution time Memory
843662 2023-09-04T11:24:54 Z Andrey Soccer Stadium (IOI23_soccer) C++17
64 / 100
 395 ms 71452 KB 
#include "soccer.h"
#include<bits/stdc++.h>
using namespace std;

int haha[700][700];
int l[700][700];
int r[700][700];
int n;

int calc(int a) {
    vector<pair<int,int>> wut(0);
    for(int i = 0; i < n; i++) {
        wut.push_back({l[i][a],r[i][a]});
    }
    int dp[n][n];
    int ans = 0;
    pair<int,int> yay[n][n];
    for(int i = 0; i < n; i++) {
        if(wut[i].first != -1) {
            dp[i][i] = wut[i].first+wut[i].second+1;
            ans = max(ans,dp[i][i]);
        }
        else {
            dp[i][i] = 0;
        }
        yay[i][i] = wut[i];
    }
    for(int i = 1; i < n; i++) {
        for(int j = 0; j < n-i; j++) {
            int k = i;
            i = j+i;
            swap(i,j);
            yay[i][j] = {min(yay[i][j-1].first,yay[j][j].first),min(yay[i][j-1].second,yay[j][j].second)};
            if(yay[i][j].first == -1) {
                dp[i][j] = 0;
            }
            else {
                dp[i][j] = dp[i][j-1]+yay[i][j].first+yay[i][j].second+1;
                dp[i][j] = max(dp[i][j],dp[i+1][j]+yay[i][j].first+yay[i][j].second+1);
                ans = max(ans,dp[i][j]);
            }
            swap(i,j);
            i = k;
        }
    }
    return ans;
}

int biggest_stadium(int N, std::vector<std::vector<int>> f)
{
    n = N;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            haha[i][j] = f[i][j];
        }
    }
    for(int i = 0; i < n; i++) {
        if(haha[i][0]) {
            l[i][0] = -1;
        }
        else {
            l[i][0] = 0;
        }
        for(int j = 1; j < n; j++) {
            if(haha[i][j]) {
                l[i][j] = -1;
            }
            else {
                l[i][j] = l[i][j-1]+1;
            }
        }
        if(haha[i][n-1]) {
            r[i][n-1] = -1;
        }
        else {
            r[i][n-1] = 0;
        }
        for(int j = n-2; j >= 0; j--) {
            if(haha[i][j]) {
                r[i][j] = -1;
            }
            else {
                r[i][j] = r[i][j+1]+1;
            }
        }
    }
    int ans = 0;
    for(int i = 0; i < n; i++) {
        ans = max(ans,calc(i));
    }
    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB ok
2 Correct 1 ms 4440 KB ok
3 Correct 1 ms 4440 KB ok
4 Correct 1 ms 4440 KB ok
5 Correct 1 ms 4440 KB ok
6 Correct 1 ms 4440 KB ok
7 Correct 5 ms 4696 KB ok
8 Correct 375 ms 10556 KB ok
9 Runtime error 264 ms 71452 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB ok
2 Correct 1 ms 4440 KB ok
3 Correct 1 ms 4440 KB ok
4 Correct 1 ms 4440 KB ok
5 Correct 1 ms 4440 KB ok
6 Correct 1 ms 4440 KB ok
7 Correct 1 ms 4440 KB ok
8 Correct 1 ms 4440 KB ok
9 Correct 1 ms 4440 KB ok
10 Correct 1 ms 4440 KB ok
11 Correct 1 ms 4440 KB ok
12 Correct 1 ms 4444 KB ok
13 Correct 1 ms 4444 KB ok

Subtask #3
22.0 / 22.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB ok
2 Correct 1 ms 4440 KB ok
3 Correct 1 ms 4440 KB ok
4 Correct 1 ms 4440 KB ok
5 Correct 1 ms 4440 KB ok
6 Correct 1 ms 4440 KB ok
7 Correct 1 ms 4440 KB ok
8 Correct 1 ms 4440 KB ok
9 Correct 1 ms 4440 KB ok
10 Correct 1 ms 4440 KB ok
11 Correct 1 ms 4440 KB ok
12 Correct 1 ms 4440 KB ok
13 Correct 1 ms 4440 KB ok
14 Correct 1 ms 4440 KB ok
15 Correct 1 ms 4444 KB ok
16 Correct 1 ms 4444 KB ok
17 Correct 1 ms 4440 KB ok
18 Correct 1 ms 4440 KB ok
19 Correct 1 ms 4440 KB ok
20 Correct 1 ms 4440 KB ok
21 Correct 1 ms 4440 KB ok
22 Correct 1 ms 4440 KB ok
23 Correct 1 ms 4444 KB ok
24 Correct 1 ms 4444 KB ok
25 Correct 1 ms 4440 KB ok
26 Correct 1 ms 4440 KB ok
27 Correct 1 ms 4444 KB ok
28 Correct 1 ms 4440 KB ok
29 Correct 1 ms 4440 KB ok
30 Correct 1 ms 4440 KB ok
31 Correct 1 ms 4440 KB ok
32 Correct 1 ms 4444 KB ok
33 Correct 1 ms 4440 KB ok
34 Correct 1 ms 4440 KB ok
35 Correct 1 ms 4440 KB ok
36 Correct 1 ms 4440 KB ok
37 Correct 1 ms 4440 KB ok
38 Correct 1 ms 4696 KB ok
39 Correct 1 ms 4440 KB ok
40 Correct 1 ms 4444 KB ok
41 Correct 1 ms 4440 KB ok
42 Correct 321 ms 10548 KB ok
43 Correct 326 ms 10328 KB ok
44 Correct 351 ms 10328 KB ok
45 Correct 370 ms 10576 KB ok
46 Correct 343 ms 10484 KB ok
47 Correct 395 ms 10552 KB ok
48 Correct 342 ms 10576 KB ok
49 Correct 346 ms 10328 KB ok
50 Correct 342 ms 10328 KB ok
51 Correct 343 ms 10556 KB ok
52 Correct 329 ms 10552 KB ok
53 Correct 309 ms 10328 KB ok
54 Correct 310 ms 10328 KB ok
55 Correct 325 ms 10556 KB ok
56 Correct 325 ms 10552 KB ok
57 Correct 356 ms 10328 KB ok
58 Correct 384 ms 10548 KB ok
59 Correct 355 ms 10548 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB ok
2 Correct 1 ms 4440 KB ok
3 Correct 1 ms 4440 KB ok
4 Correct 1 ms 4440 KB ok
5 Correct 1 ms 4440 KB ok
6 Correct 1 ms 4440 KB ok
7 Correct 1 ms 4440 KB ok
8 Correct 5 ms 4696 KB ok
9 Correct 375 ms 10556 KB ok
10 Runtime error 264 ms 71452 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -