oj.uz

Submission #1110379

# Submission time Handle Problem Language Result Execution time Memory
1110379 2024-11-09T11:03:38 Z jerzyk Soccer Stadium (IOI23_soccer) C++17
24 / 100
 236 ms 88904 KB 
#include <bits/stdc++.h>
#include "soccer.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 2'007;
int tab[N][N], il[N][N], nxt[N][N];
vector<pair<int, int>> ed[N];

map<pair<pair<int, int>, pair<int, int>>, int> num;
pair<pair<int, int>, pair<int, int>> pos[N * N];
int dp[N * N], wch[N * N];

void Cnt(int n)
{
    for(int i = 1; i <= n; ++i)
        nxt[i][n + 1] = n + 1;
    for(int i = 1; i <= n; ++i)
        for(int j = n; j >= 1; --j)
        {
            nxt[i][j] = nxt[i][j + 1];
            il[i][j] = il[i][j + 1] + 1;
            if(tab[i][j] == 0) nxt[i][j] = j;
            else il[i][j] = 0;
        }
}

int FU(int i, int j, int x)
{
    while(il[i - 1][j] >= x)
        --i;
    return i;
}

int FD(int i, int j, int x)
{
    while(il[i + 1][j] >= x)
        ++i;
    return i;
}

int GenG(int n)
{
    int cnt = 0, v;
    queue<int> q;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
        {
            if((j != 1 && tab[i][j - 1] == 0) || tab[i][j] == 1) continue;
            int u = FU(i, j, il[i][j]), d = FD(i, j, il[i][j]);
            pair<pair<int, int>, pair<int, int>> wsp = make_pair(make_pair(u, j), make_pair(d, j + il[i][j] - 1));
            if(num.find(wsp) != num.end()) continue;
            ++cnt;
            num[wsp] = cnt; pos[cnt] = wsp;
            q.push(cnt);
            ed[0].pb(make_pair(cnt, (d - u + 1) * il[i][j]));
        }
    //cerr << "XDD\n";
    while(q.size() > 0)
    {
        v = q.front(); q.pop();
        //cerr << "Gen: " << v << " " << pos[v].st.st << " " << pos[v].st.nd << " " << pos[v].nd.st << " " << pos[v].nd.nd << "\n";
        for(int r = 0; r < 2; ++r)
        {
            //cerr << r << "\n";
            int i1 = pos[v].st.st, i2 = pos[v].nd.st;
            int cr = i1 - 1;
            int j = pos[v].st.nd;
            if(r == 1)
                cr = i2 + 1;

            j = nxt[cr][j];
            while(j <= pos[v].nd.nd && cr != 0 && cr != n + 1)
            {
                //cerr << "B " << j << "\n";
                int dis = min(il[cr][j], pos[v].nd.nd - j + 1);
                int u = FU(i1, j, dis), d = FD(i2, j, dis);
                pair<pair<int, int>, pair<int, int>> wsp = make_pair(make_pair(u, j), make_pair(d, j + dis - 1));
                //cerr << "Ne: " << j << " " << dis << " " << u << " " << d << "\n";
                int ne;
                if(num.find(wsp) != num.end())
                    ne = num[wsp];
                else
                {
                    ++cnt; num[wsp] = cnt;
                    pos[cnt] = wsp;
                    ne = cnt;
                }
                //cerr << ne << "\n";
                ed[v].pb(make_pair(ne, (i1 - u + d - i2) * dis));
                j += il[cr][j]; j = nxt[cr][j];
            }
            //cerr << "E\n";
        }
    }
    return cnt;
}

void Tsort(int n)
{
    int v;
    queue<int> q;
    for(int i = 0; i <= n; ++i)
        for(int j = 0; j < (int)ed[i].size(); ++j)
            ++wch[ed[i][j].st];
    for(int i = 0; i <= n; ++i)
        if(wch[i] == 0)
            q.push(i);
    while(q.size() > 0)
    {
        v = q.front(); q.pop();
        for(int i = 0; i < (int)ed[v].size(); ++i)
        {
            dp[ed[v][i].st] = max(dp[ed[v][i].st], dp[v] + ed[v][i].nd);
            --wch[ed[v][i].st];
            if(wch[ed[v][i].st] == 0)
                q.push(ed[v][i].st);
        }
    }
}

int biggest_stadium(int _N, vector<vector<int>> _F)
{
    int n = _N, m;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            tab[i][j] = _F[i - 1][j - 1];
    Cnt(n);
    m = GenG(n);
    Tsort(m);
    int ans = 0;
    for(int i = 1; i <= m; ++i)
        ans = max(ans, dp[i]);
        
    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6600 KB ok
2 Correct 1 ms 6480 KB ok
3 Correct 2 ms 6480 KB ok
4 Correct 1 ms 6648 KB ok
5 Correct 1 ms 6596 KB ok
6 Correct 1 ms 6480 KB ok
7 Correct 3 ms 6992 KB ok
8 Correct 18 ms 18000 KB ok
9 Correct 236 ms 88904 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6600 KB ok
2 Correct 1 ms 6480 KB ok
3 Correct 2 ms 6480 KB ok
4 Correct 2 ms 6652 KB ok
5 Correct 2 ms 6480 KB ok
6 Correct 2 ms 6480 KB ok
7 Correct 2 ms 6736 KB ok
8 Correct 2 ms 6480 KB ok
9 Correct 2 ms 6480 KB ok
10 Correct 2 ms 6480 KB ok
11 Correct 1 ms 6648 KB ok
12 Correct 1 ms 6480 KB ok
13 Correct 2 ms 6480 KB ok

Subtask #3
5.5 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6480 KB ok
2 Correct 2 ms 6600 KB ok
3 Correct 1 ms 6480 KB ok
4 Correct 2 ms 6480 KB ok
5 Correct 2 ms 6652 KB ok
6 Correct 2 ms 6480 KB ok
7 Correct 2 ms 6480 KB ok
8 Correct 2 ms 6736 KB ok
9 Correct 2 ms 6480 KB ok
10 Correct 2 ms 6480 KB ok
11 Correct 2 ms 6480 KB ok
12 Correct 1 ms 6648 KB ok
13 Correct 1 ms 6480 KB ok
14 Correct 2 ms 6480 KB ok
15 Correct 2 ms 6480 KB ok
16 Correct 2 ms 6480 KB ok
17 Partially correct 2 ms 6644 KB partial
18 Correct 2 ms 6480 KB ok
19 Correct 2 ms 6480 KB ok
20 Correct 1 ms 6480 KB ok
21 Correct 1 ms 6652 KB ok
22 Correct 1 ms 6480 KB ok
23 Correct 1 ms 6492 KB ok
24 Correct 1 ms 6480 KB ok
25 Partially correct 2 ms 6480 KB partial
26 Partially correct 2 ms 6480 KB partial

Subtask #4
4.5 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6480 KB ok
2 Correct 2 ms 6600 KB ok
3 Correct 1 ms 6480 KB ok
4 Correct 2 ms 6480 KB ok
5 Correct 1 ms 6648 KB ok
6 Correct 2 ms 6480 KB ok
7 Correct 2 ms 6652 KB ok
8 Correct 2 ms 6480 KB ok
9 Correct 2 ms 6480 KB ok
10 Correct 2 ms 6736 KB ok
11 Correct 2 ms 6480 KB ok
12 Correct 2 ms 6480 KB ok
13 Correct 2 ms 6480 KB ok
14 Correct 1 ms 6648 KB ok
15 Correct 1 ms 6480 KB ok
16 Correct 2 ms 6480 KB ok
17 Correct 2 ms 6480 KB ok
18 Correct 2 ms 6480 KB ok
19 Partially correct 2 ms 6644 KB partial
20 Correct 2 ms 6480 KB ok
21 Correct 2 ms 6480 KB ok
22 Correct 1 ms 6480 KB ok
23 Correct 1 ms 6652 KB ok
24 Correct 1 ms 6480 KB ok
25 Correct 1 ms 6492 KB ok
26 Correct 1 ms 6480 KB ok
27 Partially correct 2 ms 6480 KB partial
28 Partially correct 2 ms 6480 KB partial
29 Correct 1 ms 6480 KB ok
30 Correct 2 ms 6736 KB ok
31 Correct 2 ms 6736 KB ok
32 Correct 3 ms 6736 KB ok
33 Correct 2 ms 6736 KB ok
34 Correct 1 ms 6596 KB ok
35 Correct 1 ms 6736 KB ok
36 Correct 2 ms 6908 KB ok
37 Partially correct 2 ms 6736 KB partial
38 Partially correct 2 ms 6908 KB partial
39 Partially correct 2 ms 6908 KB partial
40 Correct 1 ms 6904 KB ok
41 Partially correct 1 ms 6736 KB partial

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6480 KB ok
2 Correct 2 ms 6600 KB ok
3 Correct 1 ms 6480 KB ok
4 Correct 2 ms 6480 KB ok
5 Correct 1 ms 6648 KB ok
6 Correct 2 ms 6480 KB ok
7 Correct 2 ms 6652 KB ok
8 Correct 2 ms 6480 KB ok
9 Correct 2 ms 6480 KB ok
10 Correct 2 ms 6736 KB ok
11 Correct 2 ms 6480 KB ok
12 Correct 2 ms 6480 KB ok
13 Correct 2 ms 6480 KB ok
14 Correct 1 ms 6648 KB ok
15 Correct 1 ms 6480 KB ok
16 Correct 2 ms 6480 KB ok
17 Correct 2 ms 6480 KB ok
18 Correct 2 ms 6480 KB ok
19 Partially correct 2 ms 6644 KB partial
20 Correct 2 ms 6480 KB ok
21 Correct 2 ms 6480 KB ok
22 Correct 1 ms 6480 KB ok
23 Correct 1 ms 6652 KB ok
24 Correct 1 ms 6480 KB ok
25 Correct 1 ms 6492 KB ok
26 Correct 1 ms 6480 KB ok
27 Partially correct 2 ms 6480 KB partial
28 Partially correct 2 ms 6480 KB partial
29 Correct 1 ms 6480 KB ok
30 Correct 2 ms 6736 KB ok
31 Correct 2 ms 6736 KB ok
32 Correct 3 ms 6736 KB ok
33 Correct 2 ms 6736 KB ok
34 Correct 1 ms 6596 KB ok
35 Correct 1 ms 6736 KB ok
36 Correct 2 ms 6908 KB ok
37 Partially correct 2 ms 6736 KB partial
38 Partially correct 2 ms 6908 KB partial
39 Partially correct 2 ms 6908 KB partial
40 Correct 1 ms 6904 KB ok
41 Partially correct 1 ms 6736 KB partial
42 Runtime error 61 ms 39876 KB Execution killed with signal 11
43 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6480 KB ok
2 Correct 2 ms 6600 KB ok
3 Correct 1 ms 6480 KB ok
4 Correct 2 ms 6480 KB ok
5 Correct 1 ms 6648 KB ok
6 Correct 1 ms 6596 KB ok
7 Correct 1 ms 6480 KB ok
8 Correct 3 ms 6992 KB ok
9 Correct 18 ms 18000 KB ok
10 Correct 236 ms 88904 KB ok
11 Correct 2 ms 6480 KB ok
12 Correct 2 ms 6652 KB ok
13 Correct 2 ms 6480 KB ok
14 Correct 2 ms 6480 KB ok
15 Correct 2 ms 6736 KB ok
16 Correct 2 ms 6480 KB ok
17 Correct 2 ms 6480 KB ok
18 Correct 2 ms 6480 KB ok
19 Correct 1 ms 6648 KB ok
20 Correct 1 ms 6480 KB ok
21 Correct 2 ms 6480 KB ok
22 Correct 2 ms 6480 KB ok
23 Correct 2 ms 6480 KB ok
24 Partially correct 2 ms 6644 KB partial
25 Correct 2 ms 6480 KB ok
26 Correct 2 ms 6480 KB ok
27 Correct 1 ms 6480 KB ok
28 Correct 1 ms 6652 KB ok
29 Correct 1 ms 6480 KB ok
30 Correct 1 ms 6492 KB ok
31 Correct 1 ms 6480 KB ok
32 Partially correct 2 ms 6480 KB partial
33 Partially correct 2 ms 6480 KB partial
34 Correct 1 ms 6480 KB ok
35 Correct 2 ms 6736 KB ok
36 Correct 2 ms 6736 KB ok
37 Correct 3 ms 6736 KB ok
38 Correct 2 ms 6736 KB ok
39 Correct 1 ms 6596 KB ok
40 Correct 1 ms 6736 KB ok
41 Correct 2 ms 6908 KB ok
42 Partially correct 2 ms 6736 KB partial
43 Partially correct 2 ms 6908 KB partial
44 Partially correct 2 ms 6908 KB partial
45 Correct 1 ms 6904 KB ok
46 Partially correct 1 ms 6736 KB partial
47 Runtime error 61 ms 39876 KB Execution killed with signal 11
48 Halted 0 ms 0 KB -