oj.uz

Submission #954408

# Submission time Handle Problem Language Result Execution time Memory
954408 2024-03-27T19:56:04 Z Macker Meetings (IOI18_meetings) C++17
19 / 100
 5500 ms 8328 KB 
#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
#define int ll
typedef pair<int, int> pii;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define FOR(i, n) for (int i = 0; i < n; i++)

int get_mn(vector<int> v){
    int n = v.size();
    vector<int> res(n, 0);
    FOR(w, 2){
        stack<pair<int, int>> s;
        s.push({INT_MAX, -1});
        int cur = 0;
        FOR(i, n){
            while(s.top().ff <= v[i]){
                auto [h, j] = s.top(); s.pop();
                cur -= h * (j - s.top().ss);
            }
            cur += v[i] * (i - s.top().ss);
            res[w ? n - i - 1 : i] += cur;
            s.push({v[i], i});
        }
        reverse(all(v));
    }
    FOR(i, n) res[i] -= v[i];
    return *min_element(all(res));
}

vector<int> minimum_costs(vector<signed> H, vector<signed> L, vector<signed> R) {
    int q = L.size();
    int n = H.size();
    vector<int> res(q);
    for (int j = 0; j < q; ++j) {
        vector<int> v;
        for (int i = L[j]; i <= R[j]; i++) {
            v.push_back(H[i]);
        }
        res[j] = get_mn(v);
    }
    return res;
}

Compilation message

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:39:9: warning: unused variable 'n' [-Wunused-variable]
   39 |     int n = H.size();
      |         ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 278 ms 924 KB Output is correct
11 Correct 974 ms 1652 KB Output is correct
12 Correct 273 ms 1236 KB Output is correct
13 Correct 966 ms 1068 KB Output is correct
14 Correct 219 ms 892 KB Output is correct
15 Correct 221 ms 916 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 4024 ms 3008 KB Output is correct
3 Execution timed out 5550 ms 8328 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 4024 ms 3008 KB Output is correct
3 Execution timed out 5550 ms 8328 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 278 ms 924 KB Output is correct
11 Correct 974 ms 1652 KB Output is correct
12 Correct 273 ms 1236 KB Output is correct
13 Correct 966 ms 1068 KB Output is correct
14 Correct 219 ms 892 KB Output is correct
15 Correct 221 ms 916 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 4024 ms 3008 KB Output is correct
18 Execution timed out 5550 ms 8328 KB Time limit exceeded
19 Halted 0 ms 0 KB -