oj.uz

Submission #856959

# Submission time Handle Problem Language Result Execution time Memory
856959 2023-10-05T01:50:08 Z pirhosig Soccer Stadium (IOI23_soccer) C++17
6 / 100
 378 ms 64080 KB 
#include "soccer.h"
#include <bits/stdc++.h>
#define  R(a) for (int i = 0; i < a; ++i)
#define RR(a) for (int j = 0; j < a; ++j)
using namespace std;
typedef pair<int, int> ii;


int biggest_stadium(int N, vector<vector<int>> F)
{
    ii lrv[N][N];
    RR(N) {
        int lv = -1;
        R(N) {
            if (F[i][j]) lrv[i][j].first = (lv = -1);
            else {
                if (lv == -1) lv = i;
                lrv[i][j].first = lv;
            }
        }
        lv = -1;
        for (int i = N - 1; i >= 0; --i) {
            if (F[i][j]) lrv[i][j].second = (lv = -1);
            else {
                if (lv == -1) lv = i;
                lrv[i][j].second = lv;
            }
        }
    }

    // R(N) {
    //     RR(N) {
    //         if (!F[i][j]) cout << i << " " << j << " " << lrv[i][j].first << " " << lrv[i][j].second << endl;
    //     }
    // }

    int large = 0;
    R(N) {
        int val1[N]{};
        stack<ii> stl, str;
        int tot = 0;
        RR(N) {
            if (F[i][j]) {
                if (stl.size()) stl = stack<ii>();
                if (str.size()) str = stack<ii>();
                tot = 0;
                continue;
            }
            int lv = lrv[i][j].first;
            int rv = lrv[i][j].second;
            while (stl.size() && stl.top().first < lv) {
                tot -= (lv - stl.top().first) * (j - stl.top().second);
                stl.pop();
            }
            if (stl.empty() || stl.top().first > lv) stl.push({lv, j});

            while (str.size() && str.top().first > rv) {
                tot -= (str.top().first - rv) * (j - str.top().second);
                str.pop();
            }
            if (str.empty() || str.top().first < rv) str.push({rv, j});

            val1[j] = tot;
            tot += rv - lv + 1;
        }

        int val2[N]{};
        tot = 0;
        stl = stack<ii>();
        str = stack<ii>();
        for (int j = N - 1; j >= 0; --j) {
            if (F[i][j]) {
                if (stl.size()) stl = stack<ii>();
                if (str.size()) str = stack<ii>();
                tot = 0;
                continue;
            }
            int lv = lrv[i][j].first;
            int rv = lrv[i][j].second;
            while (stl.size() && stl.top().first < lv) {
                tot -= (lv - stl.top().first) * (stl.top().second - j);
                stl.pop();
            }
            if (stl.empty() || stl.top().first > lv) stl.push({lv, j});

            while (str.size() && str.top().first > rv) {
                tot -= (str.top().first - rv) * (str.top().second - j);
                str.pop();
            }
            if (str.empty() || str.top().first < rv) str.push({rv, j});

            val2[j] = tot;
            tot += rv - lv + 1;
        }

        RR(N) if (!F[i][j]) {
            int siz = val1[j] + val2[j] + lrv[i][j].second - lrv[i][j].first + 1;
            // cout << i << " " << j << " " << siz << " " << val1[j] << " " << val2[j] << endl;
            large = max(large, siz);
        }
    }
    
    return large;
}

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 0 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 0 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 19 ms 4252 KB ok
9 Correct 378 ms 64080 KB ok

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 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 0 ms 348 KB ok
7 Incorrect 0 ms 348 KB wrong
8 Halted 0 ms 0 KB -

Subtask #3
0.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 0 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 0 ms 348 KB ok
8 Incorrect 0 ms 348 KB wrong
9 Halted 0 ms 0 KB -

Subtask #4
0.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 0 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 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Incorrect 0 ms 348 KB wrong
11 Halted 0 ms 0 KB -

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 0 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 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Incorrect 0 ms 348 KB wrong
11 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 0 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 0 ms 348 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 19 ms 4252 KB ok
10 Correct 378 ms 64080 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 Incorrect 0 ms 348 KB wrong
16 Halted 0 ms 0 KB -