oj.uz

Submission #1029816

# Submission time Handle Problem Language Result Execution time Memory
1029816 2024-07-21T11:16:30 Z lucri Soccer Stadium (IOI23_soccer) C++17
1.5 / 100
 1603 ms 210000 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({down-up,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 344 KB ok

Subtask #1
1.5 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 448 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 444 KB ok
7 Correct 4 ms 1372 KB ok
8 Partially correct 88 ms 15444 KB partial
9 Partially correct 1603 ms 210000 KB partial

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 448 KB ok
2 Correct 0 ms 348 KB ok
3 Partially correct 0 ms 600 KB partial
4 Partially correct 0 ms 344 KB partial
5 Correct 0 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 0 ms 348 KB ok
10 Partially correct 0 ms 348 KB partial
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Incorrect 0 ms 348 KB wrong
14 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 1 ms 448 KB ok
3 Correct 0 ms 348 KB ok
4 Partially correct 0 ms 600 KB partial
5 Partially correct 0 ms 344 KB partial
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Partially correct 0 ms 348 KB partial
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Incorrect 0 ms 348 KB wrong
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 1 ms 448 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Partially correct 0 ms 600 KB partial
7 Partially correct 0 ms 344 KB partial
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 0 ms 348 KB ok
13 Partially correct 0 ms 348 KB partial
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Incorrect 0 ms 348 KB wrong
17 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 1 ms 448 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Partially correct 0 ms 600 KB partial
7 Partially correct 0 ms 344 KB partial
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 0 ms 348 KB ok
13 Partially correct 0 ms 348 KB partial
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Incorrect 0 ms 348 KB wrong
17 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 1 ms 448 KB ok
3 Correct 0 ms 348 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 0 ms 444 KB ok
8 Correct 4 ms 1372 KB ok
9 Partially correct 88 ms 15444 KB partial
10 Partially correct 1603 ms 210000 KB partial
11 Partially correct 0 ms 600 KB partial
12 Partially correct 0 ms 344 KB partial
13 Correct 0 ms 348 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 Partially correct 0 ms 348 KB partial
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Incorrect 0 ms 348 KB wrong
22 Halted 0 ms 0 KB -