oj.uz

Submission #1108893

# Submission time Handle Problem Language Result Execution time Memory
1108893 2024-11-05T15:45:32 Z jerzyk Soccer Stadium (IOI23_soccer) C++17
6 / 100
 304 ms 94772 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];
int nxt[N][N][2];
int dod[N][N];

void Cnt(int n)
{
    for(int i = 1; i <= n; ++i)
    {
        for(int r = 0; r < 2; ++r)
            {nxt[i][0][r] = -1; nxt[i][n + 1][r] = -1;}
        for(int r = 0; r < 2; ++r)
        {
            vector<int> cur; int s = 0;
            cur.pb(0);
            for(int j = 1; j <= n; ++j)
            {
                while(nxt[i][cur.back()][r] >= nxt[i][j][r])
                {
                    int xd = cur.back(); cur.pop_back();
                    s -= (xd - cur.back()) * nxt[i][xd][r];
                }
                s += (j - cur.back()) * nxt[i][j][r];
                //if(r == 1)
                    //cout << i << " " << j << " " << nxt[i][j][r] << " " << cur.back() << " " << s << "\n";
                cur.pb(j);
                dod[i][j] += s;
            }
            cur.clear(); s = 0;
            cur.pb(n + 1);
            for(int j = n; j >= 1; --j)
            {
                while(nxt[i][cur.back()][r] >= nxt[i][j][r])
                {
                    int xd = cur.back(); cur.pop_back();
                    s -= (cur.back() - xd) * nxt[i][xd][r];
                }
                s += (cur.back() - j) * nxt[i][j][r];
                //if(r == 0)
                    //cout << i << " " << j << " " << nxt[i][j][r] << " " << cur.back() << " " << s << "\n";
                cur.pb(j);
                dod[i][j] += s - nxt[i][j][r];
            }
            //cout << "\n";
        }
        int cnt = 0;
        for(int j = 1; j <= n; ++j)
        {
            ++cnt;
            if(tab[i][j] == 1) cnt = 0;
            //cout << dod[i][j] << " ";
            dod[i][j] -= cnt;
        }
        //cout << "\n";
        cnt = 0;
        for(int j = n; j >= 1; --j)
        {
            ++cnt;
            if(tab[i][j] == 1) cnt = 0;
            dod[i][j] -= (cnt - 1);
            if(tab[i][j] == 1)
                dod[i][j] = 0;
        }
    }
}

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

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB ok
2 Correct 1 ms 2384 KB ok
3 Correct 1 ms 4432 KB ok
4 Correct 1 ms 4432 KB ok
5 Correct 1 ms 2384 KB ok
6 Correct 1 ms 2384 KB ok
7 Correct 3 ms 9040 KB ok
8 Correct 21 ms 21420 KB ok
9 Correct 304 ms 94772 KB ok

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB ok
2 Correct 1 ms 2384 KB ok
3 Correct 1 ms 2384 KB ok
4 Correct 1 ms 2384 KB ok
5 Correct 1 ms 2384 KB ok
6 Correct 1 ms 4432 KB ok
7 Incorrect 1 ms 2384 KB wrong
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB ok
2 Correct 1 ms 2384 KB ok
3 Correct 1 ms 2384 KB ok
4 Correct 1 ms 2384 KB ok
5 Correct 1 ms 2384 KB ok
6 Correct 1 ms 2384 KB ok
7 Correct 1 ms 4432 KB ok
8 Incorrect 1 ms 2384 KB wrong
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB ok
2 Correct 1 ms 2384 KB ok
3 Correct 1 ms 2384 KB ok
4 Correct 1 ms 4432 KB ok
5 Correct 1 ms 4432 KB ok
6 Correct 1 ms 2384 KB ok
7 Correct 1 ms 2384 KB ok
8 Correct 1 ms 2384 KB ok
9 Correct 1 ms 4432 KB ok
10 Incorrect 1 ms 2384 KB wrong
11 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB ok
2 Correct 1 ms 2384 KB ok
3 Correct 1 ms 2384 KB ok
4 Correct 1 ms 4432 KB ok
5 Correct 1 ms 4432 KB ok
6 Correct 1 ms 2384 KB ok
7 Correct 1 ms 2384 KB ok
8 Correct 1 ms 2384 KB ok
9 Correct 1 ms 4432 KB ok
10 Incorrect 1 ms 2384 KB wrong
11 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB ok
2 Correct 1 ms 2384 KB ok
3 Correct 1 ms 2384 KB ok
4 Correct 1 ms 4432 KB ok
5 Correct 1 ms 4432 KB ok
6 Correct 1 ms 2384 KB ok
7 Correct 1 ms 2384 KB ok
8 Correct 3 ms 9040 KB ok
9 Correct 21 ms 21420 KB ok
10 Correct 304 ms 94772 KB ok
11 Correct 1 ms 2384 KB ok
12 Correct 1 ms 2384 KB ok
13 Correct 1 ms 2384 KB ok
14 Correct 1 ms 4432 KB ok
15 Incorrect 1 ms 2384 KB wrong
16 Halted 0 ms 0 KB -