oj.uz

Submission #915908

# Submission time Handle Problem Language Result Execution time Memory
915908 2024-01-24T21:39:11 Z biank Soccer Stadium (IOI23_soccer) C++17
48 / 100
 4500 ms 1960200 KB 
#include <bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define SIZE(x) (int)x.size()
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define forn(i,n) for(int i=0;i<int(n);i++)
#define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--)
#define dforn(i,n) for(int i=int(n)-1;i>=0;i--)
#define fst first
#define snd second
typedef long long ll;
typedef pair<int,int> ii;
const int MAXN = 500;
int f[MAXN][MAXN];
pair<ll,ii> dp[MAXN][MAXN][MAXN];

int n;

int left(int i, int p) {
    dforn(j,p+1) if(f[i][j]==1) return j;
    return -1;
}
int right(int i, int p) {
    forsn(j,p,n) if(f[i][j]==1) return j;
    return n;
}

pair<ll,ii> solve(int l, int r, int p) {
    if(l>r) return {0LL,{-1,n}};
    if(dp[l][r][p].fst!=-1) return dp[l][r][p];
    auto calculate = [&](pair<int,ii> prev, int i) {
        auto [val,range] = prev;
        int mini = max(range.fst, left(i,p)), maxi = min(range.snd, right(i,p));
        return (pair<ll,ii>){val+max(maxi-mini-1,0),{mini,maxi}};
    };
    return dp[l][r][p] = max(calculate(solve(l+1,r,p),l),
                            calculate(solve(l,r-1,p),r));
}

int biggest_stadium(int N, vector<vector<int>> F) {
    n=N;
    forn(i,n) forn(j,n) {
        f[i][j]=F[i][j];
    }
    forn(i,n) forn(j,n) forn(k,n) {
        dp[i][j][k].fst = -1;
    }
    ll ans = 0LL;
    forn(i,n) {
        ll curr = solve(0,n-1,i).fst;
        ans=max(ans,curr);
    }
    return int(ans);
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB ok
2 Correct 1 ms 6492 KB ok
3 Correct 3 ms 18780 KB ok
4 Correct 4 ms 20828 KB ok
5 Correct 1 ms 2396 KB ok
6 Correct 1 ms 6492 KB ok
7 Correct 101 ms 285780 KB ok
8 Execution timed out 4689 ms 1960180 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB ok
2 Correct 1 ms 6492 KB ok
3 Correct 1 ms 6488 KB ok
4 Correct 2 ms 6488 KB ok
5 Correct 1 ms 6500 KB ok
6 Correct 1 ms 6492 KB ok
7 Correct 2 ms 6492 KB ok
8 Correct 2 ms 6488 KB ok
9 Correct 1 ms 6496 KB ok
10 Correct 2 ms 6744 KB ok
11 Correct 1 ms 6492 KB ok
12 Correct 1 ms 6496 KB ok
13 Correct 1 ms 6596 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB ok
2 Correct 1 ms 6492 KB ok
3 Correct 1 ms 6492 KB ok
4 Correct 1 ms 6488 KB ok
5 Correct 2 ms 6488 KB ok
6 Correct 1 ms 6500 KB ok
7 Correct 1 ms 6492 KB ok
8 Correct 2 ms 6492 KB ok
9 Correct 2 ms 6488 KB ok
10 Correct 1 ms 6496 KB ok
11 Correct 2 ms 6744 KB ok
12 Correct 1 ms 6492 KB ok
13 Correct 1 ms 6496 KB ok
14 Correct 1 ms 6596 KB ok
15 Correct 2 ms 14684 KB ok
16 Correct 2 ms 14776 KB ok
17 Correct 3 ms 14684 KB ok
18 Correct 3 ms 14684 KB ok
19 Correct 3 ms 14684 KB ok
20 Correct 3 ms 14684 KB ok
21 Correct 3 ms 14820 KB ok
22 Correct 3 ms 14684 KB ok
23 Correct 3 ms 14688 KB ok
24 Correct 3 ms 14680 KB ok
25 Correct 3 ms 14940 KB ok
26 Correct 3 ms 14940 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB ok
2 Correct 1 ms 6492 KB ok
3 Correct 1 ms 6492 KB ok
4 Correct 3 ms 18780 KB ok
5 Correct 4 ms 20828 KB ok
6 Correct 1 ms 6488 KB ok
7 Correct 2 ms 6488 KB ok
8 Correct 1 ms 6500 KB ok
9 Correct 1 ms 6492 KB ok
10 Correct 2 ms 6492 KB ok
11 Correct 2 ms 6488 KB ok
12 Correct 1 ms 6496 KB ok
13 Correct 2 ms 6744 KB ok
14 Correct 1 ms 6492 KB ok
15 Correct 1 ms 6496 KB ok
16 Correct 1 ms 6596 KB ok
17 Correct 2 ms 14684 KB ok
18 Correct 2 ms 14776 KB ok
19 Correct 3 ms 14684 KB ok
20 Correct 3 ms 14684 KB ok
21 Correct 3 ms 14684 KB ok
22 Correct 3 ms 14684 KB ok
23 Correct 3 ms 14820 KB ok
24 Correct 3 ms 14684 KB ok
25 Correct 3 ms 14688 KB ok
26 Correct 3 ms 14680 KB ok
27 Correct 3 ms 14940 KB ok
28 Correct 3 ms 14940 KB ok
29 Correct 3 ms 14680 KB ok
30 Correct 12 ms 70244 KB ok
31 Correct 12 ms 70236 KB ok
32 Correct 11 ms 70236 KB ok
33 Correct 11 ms 70088 KB ok
34 Correct 11 ms 70260 KB ok
35 Correct 10 ms 70236 KB ok
36 Correct 11 ms 70320 KB ok
37 Correct 10 ms 70236 KB ok
38 Correct 11 ms 70404 KB ok
39 Correct 11 ms 70236 KB ok
40 Correct 10 ms 70236 KB ok
41 Correct 12 ms 70292 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB ok
2 Correct 1 ms 6492 KB ok
3 Correct 1 ms 6492 KB ok
4 Correct 3 ms 18780 KB ok
5 Correct 4 ms 20828 KB ok
6 Correct 1 ms 6488 KB ok
7 Correct 2 ms 6488 KB ok
8 Correct 1 ms 6500 KB ok
9 Correct 1 ms 6492 KB ok
10 Correct 2 ms 6492 KB ok
11 Correct 2 ms 6488 KB ok
12 Correct 1 ms 6496 KB ok
13 Correct 2 ms 6744 KB ok
14 Correct 1 ms 6492 KB ok
15 Correct 1 ms 6496 KB ok
16 Correct 1 ms 6596 KB ok
17 Correct 2 ms 14684 KB ok
18 Correct 2 ms 14776 KB ok
19 Correct 3 ms 14684 KB ok
20 Correct 3 ms 14684 KB ok
21 Correct 3 ms 14684 KB ok
22 Correct 3 ms 14684 KB ok
23 Correct 3 ms 14820 KB ok
24 Correct 3 ms 14684 KB ok
25 Correct 3 ms 14688 KB ok
26 Correct 3 ms 14680 KB ok
27 Correct 3 ms 14940 KB ok
28 Correct 3 ms 14940 KB ok
29 Correct 3 ms 14680 KB ok
30 Correct 12 ms 70244 KB ok
31 Correct 12 ms 70236 KB ok
32 Correct 11 ms 70236 KB ok
33 Correct 11 ms 70088 KB ok
34 Correct 11 ms 70260 KB ok
35 Correct 10 ms 70236 KB ok
36 Correct 11 ms 70320 KB ok
37 Correct 10 ms 70236 KB ok
38 Correct 11 ms 70404 KB ok
39 Correct 11 ms 70236 KB ok
40 Correct 10 ms 70236 KB ok
41 Correct 12 ms 70292 KB ok
42 Execution timed out 4680 ms 1960200 KB Time limit exceeded
43 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB ok
2 Correct 1 ms 6492 KB ok
3 Correct 1 ms 6492 KB ok
4 Correct 3 ms 18780 KB ok
5 Correct 4 ms 20828 KB ok
6 Correct 1 ms 2396 KB ok
7 Correct 1 ms 6492 KB ok
8 Correct 101 ms 285780 KB ok
9 Execution timed out 4689 ms 1960180 KB Time limit exceeded
10 Halted 0 ms 0 KB -