oj.uz

Submission #850575

# Submission time Handle Problem Language Result Execution time Memory
850575 2023-09-17T00:09:15 Z resting Soccer Stadium (IOI23_soccer) C++17
0 / 100
 1 ms 348 KB 
#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){
                t.push_back(j);
                d[j].pop_back();
            }
        }

        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(j);
        }
        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(auto &x : t) u[x].push_back(i);
    }
    return N * N - ans;
}

Compilation message

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 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB wrong
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB wrong
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Incorrect 0 ms 344 KB wrong
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Incorrect 0 ms 344 KB wrong
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Incorrect 0 ms 344 KB wrong
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Incorrect 0 ms 344 KB wrong
3 Halted 0 ms 0 KB -