제출 #856960

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
856960		pirhosig	축구 경기장 (IOI23_soccer)	C++17	6 / 100	397 ms	63060 KiB

soccer

#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) {
        ii 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;
            }
            val1[j].first = tot;
            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].second = tot;
            tot += rv - lv + 1;
        }

        ii 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;
            }
            val2[j].first = tot;
            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].second = tot;
            tot += rv - lv + 1;
        }

        RR(N) if (!F[i][j]) {
            int siz = max(val1[j].first + val2[j].second, val1[j].second + val2[j].first) + 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
• Subtask 1: 6 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 22
• Subtask 4: 0 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30