oj.uz

Submission #1029819

# Submission time Handle Problem Language Result Execution time Memory
1029819 2024-07-21T11:22:46 Z lucri Soccer Stadium (IOI23_soccer) C++17
54 / 100
 4500 ms 438244 KB 
#include "soccer.h"
#include <bits/stdc++.h>
int n,next[2010][2010],ans;
std::map<std::pair<std::pair<int,int>,std::pair<int,int>>,int>val;
std::priority_queue<std::pair<int,std::pair<std::pair<int,int>,std::pair<int,int>>>>q;
void adauga(int up,int down,int l,int r,int valac)
{
    std::pair<std::pair<int,int>,std::pair<int,int>>cod={{up,down},{l,r}};
    if(val.find(cod)==val.end())
    {
        q.push({up-down,cod});
        val[cod]=valac;
    }
    else
        if(valac>val[cod])
            val[cod]=valac;
    if(valac>ans)
        ans=valac;
}
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    n=N;
    for(int i=0;i<n;++i)
    {
        next[i][n]=n-1;
        for(int j=n-1;j>=0;--j)
        {
            if(F[i][j]==1)
                next[i][j]=j-1;
            else
                next[i][j]=next[i][j+1];
        }
    }
    for(int i=0;i<n;++i)
    {
        int poz=0;
        while(poz!=n)
        {
            if(next[i][poz]<poz)
                ++poz;
            else
            {
                adauga(i,i,poz,next[i][poz],next[i][poz]-poz+1);
                poz=next[i][poz]+1;
            }
        }
    }
    while(!q.empty())
    {
        std::pair<std::pair<int,int>,std::pair<int,int>>cod=q.top().second;
        q.pop();
        int up=cod.first.first;
        int down=cod.first.second;
        int l=cod.second.first;
        int r=cod.second.second;
        if(up)
        {
            int poz=l;
            while(poz<=r)
            {
                if(next[up-1][poz]>=poz)
                {
                    adauga(up-1,down,poz,std::min(next[up-1][poz],r),val[cod]+std::min(next[up-1][poz],r)-poz+1);
                    poz=next[up-1][poz]+1;
                }
                else
                    ++poz;
            }
        }
        if(down+1!=n)
        {
            int poz=l;
            while(poz<=r)
            {
                if(next[down+1][poz]>=poz)
                {
                    adauga(up,down+1,poz,std::min(next[down+1][poz],r),val[cod]+std::min(next[down+1][poz],r)-poz+1);
                    poz=next[down+1][poz]+1;
                }
                else
                    ++poz;
            }
        }
    }
    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 1 ms 348 KB ok
3 Correct 1 ms 344 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 4 ms 1372 KB ok
8 Correct 102 ms 14960 KB ok
9 Correct 1874 ms 202168 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 1 ms 348 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 1 ms 348 KB ok
7 Correct 0 ms 344 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 1 ms 344 KB ok
13 Correct 0 ms 348 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 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 1 ms 348 KB ok
8 Correct 0 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 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 444 KB ok
22 Correct 1 ms 348 KB ok
23 Correct 1 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 1 ms 348 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 1 ms 344 KB ok
5 Correct 1 ms 348 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 1 ms 348 KB ok
10 Correct 0 ms 344 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 1 ms 344 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 0 ms 348 KB ok
23 Correct 0 ms 444 KB ok
24 Correct 1 ms 348 KB ok
25 Correct 1 ms 348 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 1 ms 348 KB ok
29 Correct 0 ms 348 KB ok
30 Correct 2 ms 604 KB ok
31 Correct 1 ms 604 KB ok
32 Correct 1 ms 604 KB ok
33 Correct 0 ms 348 KB ok
34 Correct 1 ms 600 KB ok
35 Correct 1 ms 348 KB ok
36 Correct 0 ms 348 KB ok
37 Correct 0 ms 348 KB ok
38 Correct 1 ms 344 KB ok
39 Correct 1 ms 348 KB ok
40 Correct 0 ms 348 KB ok
41 Correct 1 ms 604 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 1 ms 344 KB ok
5 Correct 1 ms 348 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 1 ms 348 KB ok
10 Correct 0 ms 344 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 1 ms 344 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 0 ms 348 KB ok
23 Correct 0 ms 444 KB ok
24 Correct 1 ms 348 KB ok
25 Correct 1 ms 348 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 1 ms 348 KB ok
29 Correct 0 ms 348 KB ok
30 Correct 2 ms 604 KB ok
31 Correct 1 ms 604 KB ok
32 Correct 1 ms 604 KB ok
33 Correct 0 ms 348 KB ok
34 Correct 1 ms 600 KB ok
35 Correct 1 ms 348 KB ok
36 Correct 0 ms 348 KB ok
37 Correct 0 ms 348 KB ok
38 Correct 1 ms 344 KB ok
39 Correct 1 ms 348 KB ok
40 Correct 0 ms 348 KB ok
41 Correct 1 ms 604 KB ok
42 Correct 888 ms 78356 KB ok
43 Correct 490 ms 40920 KB ok
44 Execution timed out 4555 ms 438244 KB Time limit exceeded
45 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 1 ms 344 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 4 ms 1372 KB ok
9 Correct 102 ms 14960 KB ok
10 Correct 1874 ms 202168 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 1 ms 348 KB ok
15 Correct 0 ms 344 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 1 ms 344 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 0 ms 444 KB ok
29 Correct 1 ms 348 KB ok
30 Correct 1 ms 348 KB ok
31 Correct 0 ms 348 KB ok
32 Correct 0 ms 348 KB ok
33 Correct 1 ms 348 KB ok
34 Correct 0 ms 348 KB ok
35 Correct 2 ms 604 KB ok
36 Correct 1 ms 604 KB ok
37 Correct 1 ms 604 KB ok
38 Correct 0 ms 348 KB ok
39 Correct 1 ms 600 KB ok
40 Correct 1 ms 348 KB ok
41 Correct 0 ms 348 KB ok
42 Correct 0 ms 348 KB ok
43 Correct 1 ms 344 KB ok
44 Correct 1 ms 348 KB ok
45 Correct 0 ms 348 KB ok
46 Correct 1 ms 604 KB ok
47 Correct 888 ms 78356 KB ok
48 Correct 490 ms 40920 KB ok
49 Execution timed out 4555 ms 438244 KB Time limit exceeded
50 Halted 0 ms 0 KB -