oj.uz

Submission #1110405

# Submission time Handle Problem Language Result Execution time Memory
1110405 2024-11-09T11:36:15 Z jerzyk Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 1141820 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 * N * 10];

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

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: " << wsp.st.st << " " << wsp.st.nd << " " << wsp.nd.st << " " << wsp.nd.nd << "\n";
                int ne;
                if(num.find(wsp) != num.end())
                    ne = num[wsp];
                else
                {
                    ++cnt; num[wsp] = cnt;
                    pos[cnt] = wsp;
                    ne = cnt;
                    q.push(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 491 ms 948040 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 499 ms 948040 KB ok
2 Correct 483 ms 948116 KB ok
3 Correct 533 ms 948100 KB ok
4 Correct 561 ms 948332 KB ok
5 Correct 523 ms 948108 KB ok
6 Correct 550 ms 948040 KB ok
7 Correct 536 ms 949576 KB ok
8 Correct 580 ms 959048 KB ok
9 Correct 835 ms 1030728 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 499 ms 948040 KB ok
2 Correct 483 ms 948116 KB ok
3 Correct 527 ms 948036 KB ok
4 Correct 534 ms 948188 KB ok
5 Correct 544 ms 948040 KB ok
6 Correct 503 ms 948064 KB ok
7 Correct 536 ms 948124 KB ok
8 Correct 526 ms 948040 KB ok
9 Correct 531 ms 948040 KB ok
10 Correct 566 ms 948076 KB ok
11 Correct 543 ms 948076 KB ok
12 Correct 534 ms 948040 KB ok
13 Correct 590 ms 948064 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 948040 KB ok
2 Correct 499 ms 948040 KB ok
3 Correct 483 ms 948116 KB ok
4 Correct 527 ms 948036 KB ok
5 Correct 534 ms 948188 KB ok
6 Correct 544 ms 948040 KB ok
7 Correct 503 ms 948064 KB ok
8 Correct 536 ms 948124 KB ok
9 Correct 526 ms 948040 KB ok
10 Correct 531 ms 948040 KB ok
11 Correct 566 ms 948076 KB ok
12 Correct 543 ms 948076 KB ok
13 Correct 534 ms 948040 KB ok
14 Correct 590 ms 948064 KB ok
15 Correct 558 ms 948076 KB ok
16 Correct 583 ms 948100 KB ok
17 Correct 575 ms 948244 KB ok
18 Correct 565 ms 948212 KB ok
19 Correct 545 ms 948044 KB ok
20 Correct 567 ms 948180 KB ok
21 Correct 564 ms 948132 KB ok
22 Correct 560 ms 948108 KB ok
23 Correct 549 ms 948180 KB ok
24 Correct 562 ms 948296 KB ok
25 Correct 545 ms 948296 KB ok
26 Correct 520 ms 948144 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 948040 KB ok
2 Correct 499 ms 948040 KB ok
3 Correct 483 ms 948116 KB ok
4 Correct 533 ms 948100 KB ok
5 Correct 561 ms 948332 KB ok
6 Correct 527 ms 948036 KB ok
7 Correct 534 ms 948188 KB ok
8 Correct 544 ms 948040 KB ok
9 Correct 503 ms 948064 KB ok
10 Correct 536 ms 948124 KB ok
11 Correct 526 ms 948040 KB ok
12 Correct 531 ms 948040 KB ok
13 Correct 566 ms 948076 KB ok
14 Correct 543 ms 948076 KB ok
15 Correct 534 ms 948040 KB ok
16 Correct 590 ms 948064 KB ok
17 Correct 558 ms 948076 KB ok
18 Correct 583 ms 948100 KB ok
19 Correct 575 ms 948244 KB ok
20 Correct 565 ms 948212 KB ok
21 Correct 545 ms 948044 KB ok
22 Correct 567 ms 948180 KB ok
23 Correct 564 ms 948132 KB ok
24 Correct 560 ms 948108 KB ok
25 Correct 549 ms 948180 KB ok
26 Correct 562 ms 948296 KB ok
27 Correct 545 ms 948296 KB ok
28 Correct 520 ms 948144 KB ok
29 Correct 573 ms 948296 KB ok
30 Correct 532 ms 948392 KB ok
31 Correct 558 ms 948552 KB ok
32 Correct 560 ms 948556 KB ok
33 Correct 565 ms 948552 KB ok
34 Correct 530 ms 948356 KB ok
35 Correct 530 ms 948552 KB ok
36 Correct 546 ms 948432 KB ok
37 Correct 549 ms 948552 KB ok
38 Correct 575 ms 948552 KB ok
39 Correct 559 ms 948588 KB ok
40 Correct 561 ms 948588 KB ok
41 Correct 555 ms 948552 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 948040 KB ok
2 Correct 499 ms 948040 KB ok
3 Correct 483 ms 948116 KB ok
4 Correct 533 ms 948100 KB ok
5 Correct 561 ms 948332 KB ok
6 Correct 527 ms 948036 KB ok
7 Correct 534 ms 948188 KB ok
8 Correct 544 ms 948040 KB ok
9 Correct 503 ms 948064 KB ok
10 Correct 536 ms 948124 KB ok
11 Correct 526 ms 948040 KB ok
12 Correct 531 ms 948040 KB ok
13 Correct 566 ms 948076 KB ok
14 Correct 543 ms 948076 KB ok
15 Correct 534 ms 948040 KB ok
16 Correct 590 ms 948064 KB ok
17 Correct 558 ms 948076 KB ok
18 Correct 583 ms 948100 KB ok
19 Correct 575 ms 948244 KB ok
20 Correct 565 ms 948212 KB ok
21 Correct 545 ms 948044 KB ok
22 Correct 567 ms 948180 KB ok
23 Correct 564 ms 948132 KB ok
24 Correct 560 ms 948108 KB ok
25 Correct 549 ms 948180 KB ok
26 Correct 562 ms 948296 KB ok
27 Correct 545 ms 948296 KB ok
28 Correct 520 ms 948144 KB ok
29 Correct 573 ms 948296 KB ok
30 Correct 532 ms 948392 KB ok
31 Correct 558 ms 948552 KB ok
32 Correct 560 ms 948556 KB ok
33 Correct 565 ms 948552 KB ok
34 Correct 530 ms 948356 KB ok
35 Correct 530 ms 948552 KB ok
36 Correct 546 ms 948432 KB ok
37 Correct 549 ms 948552 KB ok
38 Correct 575 ms 948552 KB ok
39 Correct 559 ms 948588 KB ok
40 Correct 561 ms 948588 KB ok
41 Correct 555 ms 948552 KB ok
42 Correct 609 ms 966340 KB ok
43 Correct 653 ms 967616 KB ok
44 Correct 583 ms 961472 KB ok
45 Correct 569 ms 960584 KB ok
46 Correct 557 ms 964108 KB ok
47 Correct 611 ms 959568 KB ok
48 Correct 548 ms 959528 KB ok
49 Correct 551 ms 959428 KB ok
50 Correct 676 ms 960584 KB ok
51 Correct 613 ms 961540 KB ok
52 Correct 606 ms 959560 KB ok
53 Correct 621 ms 959560 KB ok
54 Correct 634 ms 959724 KB ok
55 Correct 590 ms 959648 KB ok
56 Correct 550 ms 959548 KB ok
57 Correct 582 ms 966984 KB ok
58 Correct 625 ms 967912 KB ok
59 Correct 560 ms 969032 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 948040 KB ok
2 Correct 499 ms 948040 KB ok
3 Correct 483 ms 948116 KB ok
4 Correct 533 ms 948100 KB ok
5 Correct 561 ms 948332 KB ok
6 Correct 523 ms 948108 KB ok
7 Correct 550 ms 948040 KB ok
8 Correct 536 ms 949576 KB ok
9 Correct 580 ms 959048 KB ok
10 Correct 835 ms 1030728 KB ok
11 Correct 527 ms 948036 KB ok
12 Correct 534 ms 948188 KB ok
13 Correct 544 ms 948040 KB ok
14 Correct 503 ms 948064 KB ok
15 Correct 536 ms 948124 KB ok
16 Correct 526 ms 948040 KB ok
17 Correct 531 ms 948040 KB ok
18 Correct 566 ms 948076 KB ok
19 Correct 543 ms 948076 KB ok
20 Correct 534 ms 948040 KB ok
21 Correct 590 ms 948064 KB ok
22 Correct 558 ms 948076 KB ok
23 Correct 583 ms 948100 KB ok
24 Correct 575 ms 948244 KB ok
25 Correct 565 ms 948212 KB ok
26 Correct 545 ms 948044 KB ok
27 Correct 567 ms 948180 KB ok
28 Correct 564 ms 948132 KB ok
29 Correct 560 ms 948108 KB ok
30 Correct 549 ms 948180 KB ok
31 Correct 562 ms 948296 KB ok
32 Correct 545 ms 948296 KB ok
33 Correct 520 ms 948144 KB ok
34 Correct 573 ms 948296 KB ok
35 Correct 532 ms 948392 KB ok
36 Correct 558 ms 948552 KB ok
37 Correct 560 ms 948556 KB ok
38 Correct 565 ms 948552 KB ok
39 Correct 530 ms 948356 KB ok
40 Correct 530 ms 948552 KB ok
41 Correct 546 ms 948432 KB ok
42 Correct 549 ms 948552 KB ok
43 Correct 575 ms 948552 KB ok
44 Correct 559 ms 948588 KB ok
45 Correct 561 ms 948588 KB ok
46 Correct 555 ms 948552 KB ok
47 Correct 609 ms 966340 KB ok
48 Correct 653 ms 967616 KB ok
49 Correct 583 ms 961472 KB ok
50 Correct 569 ms 960584 KB ok
51 Correct 557 ms 964108 KB ok
52 Correct 611 ms 959568 KB ok
53 Correct 548 ms 959528 KB ok
54 Correct 551 ms 959428 KB ok
55 Correct 676 ms 960584 KB ok
56 Correct 613 ms 961540 KB ok
57 Correct 606 ms 959560 KB ok
58 Correct 621 ms 959560 KB ok
59 Correct 634 ms 959724 KB ok
60 Correct 590 ms 959648 KB ok
61 Correct 550 ms 959548 KB ok
62 Correct 582 ms 966984 KB ok
63 Correct 625 ms 967912 KB ok
64 Correct 560 ms 969032 KB ok
65 Correct 1900 ms 1141820 KB ok
66 Correct 1202 ms 1114904 KB ok
67 Correct 862 ms 1067592 KB ok
68 Correct 864 ms 1039944 KB ok
69 Correct 1274 ms 1065132 KB ok
70 Correct 1586 ms 1086124 KB ok
71 Correct 918 ms 1037640 KB ok
72 Correct 812 ms 1034460 KB ok
73 Correct 804 ms 1034616 KB ok
74 Correct 766 ms 1034568 KB ok
75 Correct 808 ms 1036620 KB ok
76 Execution timed out 4630 ms 1035064 KB Time limit exceeded
77 Halted 0 ms 0 KB -