oj.uz

Submission #969731

# Submission time Handle Problem Language Result Execution time Memory
969731 2024-04-25T14:07:38 Z BestCrazyNoob Meetings (IOI18_meetings) C++17
19 / 100
 5500 ms 5540 KB 
#include "meetings.h"
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;
constexpr int INF = 2e9;

ll solve(vector<int> H) {
    vector<ll> ans(H.size(), 0);
    vector<int> s;
    ll curr = 0;
    for (int i = 0; i < H.size(); i++) {
        while (s.size() >= 1 && H[i] > H[s.back()]) {
            const int d = s.size() == 1 ? s.back() + 1 : s.back() - s[s.size()-2];
            curr += d * (ll)(H[i] - H[s.back()]);
            s.pop_back();
        }
        s.push_back(i);
        curr += H[i];
        ans[i] = curr;
    }
    curr = 0;
    s.resize(0);
    for (int i = H.size()-1; i >= 0; i--) {
        while (s.size() >= 1 && H[i] > H[s.back()]) {
            const int d = s.size() == 1 ? H.size() - s.back() : s[s.size()-2] - s.back();
            curr += d * (ll)(H[i] - H[s.back()]);
            s.pop_back();
        }
        s.push_back(i);
        ans[i] += curr;
        curr += H[i];
    }
    return *min_element(ans.begin(), ans.end());
}

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    vector<ll> C(L.size());
    for (int q = 0; q < L.size(); q++) {
        C[q] = solve(vector<int>(H.begin() + L[q], H.begin() + R[q] + 1));
    }
    return C;
}

Compilation message

meetings.cpp: In function 'll solve(std::vector<int>)':
meetings.cpp:13:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for (int i = 0; i < H.size(); i++) {
      |                     ~~^~~~~~~~~~
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (int q = 0; q < L.size(); q++) {
      |                     ~~^~~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 436 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 508 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 147 ms 752 KB Output is correct
11 Correct 537 ms 604 KB Output is correct
12 Correct 146 ms 796 KB Output is correct
13 Correct 516 ms 756 KB Output is correct
14 Correct 65 ms 808 KB Output is correct
15 Correct 77 ms 748 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1649 ms 1792 KB Output is correct
3 Execution timed out 5554 ms 5540 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1649 ms 1792 KB Output is correct
3 Execution timed out 5554 ms 5540 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 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 436 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 508 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 147 ms 752 KB Output is correct
11 Correct 537 ms 604 KB Output is correct
12 Correct 146 ms 796 KB Output is correct
13 Correct 516 ms 756 KB Output is correct
14 Correct 65 ms 808 KB Output is correct
15 Correct 77 ms 748 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1649 ms 1792 KB Output is correct
18 Execution timed out 5554 ms 5540 KB Time limit exceeded
19 Halted 0 ms 0 KB -