oj.uz

Submission #850573

# Submission time Handle Problem Language Result Execution time Memory
850573 2023-09-16T23:42:15 Z resting Soccer Stadium (IOI23_soccer) C++17
6 / 100
 322 ms 32340 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> 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);

        for(int j = 0; j <= N; j++){
            int tmp = b[j] + c[N-j] + f[j] + g[N-j];
            ans = min(ans, tmp);
        }

        for(int j = 0; j < N; j++){
            if(d[j].back() == i){
                d[j].pop_back();
                u[j].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 344 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 1 ms 348 KB ok
3 Correct 1 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 21 ms 2396 KB ok
9 Correct 322 ms 32340 KB ok

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 1 ms 348 KB ok
3 Partially correct 0 ms 344 KB partial
4 Partially correct 0 ms 348 KB partial
5 Correct 1 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Incorrect 1 ms 348 KB wrong
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 1 ms 348 KB ok
4 Partially correct 0 ms 344 KB partial
5 Partially correct 0 ms 348 KB partial
6 Correct 1 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Incorrect 1 ms 348 KB wrong
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Partially correct 0 ms 344 KB partial
7 Partially correct 0 ms 348 KB partial
8 Correct 1 ms 348 KB ok
9 Correct 1 ms 348 KB ok
10 Incorrect 1 ms 348 KB wrong
11 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Partially correct 0 ms 344 KB partial
7 Partially correct 0 ms 348 KB partial
8 Correct 1 ms 348 KB ok
9 Correct 1 ms 348 KB ok
10 Incorrect 1 ms 348 KB wrong
11 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 1 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 21 ms 2396 KB ok
10 Correct 322 ms 32340 KB ok
11 Partially correct 0 ms 344 KB partial
12 Partially correct 0 ms 348 KB partial
13 Correct 1 ms 348 KB ok
14 Correct 1 ms 348 KB ok
15 Incorrect 1 ms 348 KB wrong
16 Halted 0 ms 0 KB -