Submission #850576

#	Time	Username	Problem	Language	Result	Execution time	Memory
850576		resting	Soccer Stadium (IOI23_soccer)	C++17	1.50 / 100	413 ms	32248 KiB

soccer

#include <bits/stdc++.h>
using namespace std;
//#include "soccer.h"

#define int long long

vector<int> monostack(vector<int> h){
    vector<int> res = {0};
    vector<int> x = {-1}, y;
    int cur = 0;
    for(int i = 0; i < h.size(); i++){
        while(y.size() && h[i] >= y.back()){
            cur -= y.back() * (x.back() - x[x.size()-2]);
            y.pop_back();
            x.pop_back();
        }
        cur += h[i] * (i - x.back());
        y.push_back(h[i]);
        x.push_back(i);
        res.push_back(cur);
    }
    return res; // is this really the easiest way
    //ill have to perfect it 
}

int32_t biggest_stadium(int32_t N, std::vector<std::vector<int32_t>> F)
{
    vector<vector<int>> u(N, {-1}), d(N, {N});
    for(int i = N-1; i >= 0; i--){
        for(int j = 0; j < N; j++){
            if(F[i][j] == 1){
                d[j].push_back(i);
            }
        }
    }
    int ans = N * N;
    for(int i = 0; i < N; i++){

        vector<int> t;
        for(int j = 0; j < N; j++){
            if(d[j].back() == i){
                u[j].push_back(i);
            }
        }

        vector<int> a;
        for(int j = 0; j < N; j++) a.push_back(u[j].back()+1);
        vector<int> b=  monostack(a);
        reverse(a.begin(), a.end());
        vector<int> c=  monostack(a);

        vector<int> e;
        for(int j = 0; j < N; j++) e.push_back(N - d[j].back());
        vector<int> f = monostack(e);
        reverse(e.begin(), e.end());
        vector<int> g= monostack(e);

        vector<int> l; int p = -1;
        for(int j = 0; j < N; j++) {
            if(F[i][j] == 1) p = j;
            l.push_back(p);
        }
        p = N;
        vector<int> r;
        for(int j = N-1; j >= 0; j--){
            if(F[i][j] == 1) p = j;
            r.push_back(p);
        }
        reverse(r.begin(), r.end());
        
        for(int j = 0; j < N; j++){
            if(F[i][j] == 1) continue;

            int tmp = b[j] + c[N-j-1] + f[j] + g[N-j-1] 
            - (l[j]+1) - (N-r[j]) + (u[j].back()+1) + (N-d[j].back());
            ans = min(ans, tmp);
        }

        for(int j = 0; j < N; j++){
            if(d[j].back() == i){
                d[j].pop_back();
            }
        }
    }
    return N * N - ans;
}

Compilation message (stderr)

soccer.cpp: In function 'std::vector<long long int> monostack(std::vector<long long int>)':
soccer.cpp:11:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for(int i = 0; i < h.size(); i++){
      |                    ~~^~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 1.5 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 22
• Subtask 4: 0 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30