oj.uz

Submission #418606

# Submission time Handle Problem Language Result Execution time Memory
418606 2021-06-05T15:35:37 Z FlippenFaz Meetings (IOI18_meetings) C++11
19 / 100
 5500 ms 6160 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
vector<pair<int,int>> highestNeighs;

ll calc_cost(const vector<int> &h, int left, int right, int mid) {
    //cout << "CALC " << left << " TO " << right << " USING MID: " << mid << endl; 
    ll sum = -h[mid];
    int temp = mid;
    while (temp <= right) {
        //cout << "TEMP, HIGHEST RIGHT: " << temp << " " << highestNeighs[temp].second << endl;
        //cout << "TEMP HEIGHT: " << h[temp] << endl;
        //cout << "CURSUM: " << sum << endl;
        sum += ll(h[temp]) * (min(highestNeighs[temp].second-1, right) - temp+1);
        //cout << "NEW SUM: " << sum << endl;
        temp =  highestNeighs[temp].second;
    }
    temp = mid;
    while (temp >= left) {
        //cout << "TEMP, HIGHEST Left: " << temp << " " << highestNeighs[temp].first << endl;
        //cout << "TEMP HEIGHT: " << h[temp] << endl;
        //cout << "CURSUM: " << sum << endl;
        sum += ll(h[temp]) * (temp - max(highestNeighs[temp].first+1, left) + 1);
        //cout << "NEW SUM: " << sum << endl;
        temp =  highestNeighs[temp].first;
    }
    //cout << "GOT: " << sum << endl;
    return sum;
    
}

vector<ll> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {

    vector<ll> ans;
    

    for (int i = 0; i < h.size(); i++) {
        int left = -1;
        int right = h.size()+1;
        for (int j = i-1; j >= 0; j--) {
            if (h[j] > h[i]) {
                //cout << "HIGHEST LEFT OF " << i << " IS " << j;
                left = j;
                break;
            }
        }
        for (int j = i+1; j < h.size(); j++) {
            if (h[j] > h[i]) {
                right = j;
                break;
            }
        }
        highestNeighs.push_back(make_pair(left, right));

    }


    for (int i = 0; i < l.size(); i++) {
        ll mn = INT64_MAX;
        for (int j = l[i]; j <= r[i]; j++) {
            mn = min(mn, calc_cost(h, l[i], r[i], j));
        }
        ans.push_back(mn);
    }

    return ans;

}

Compilation message

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (int i = 0; i < h.size(); i++) {
      |                     ~~^~~~~~~~~~
meetings.cpp:48:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for (int j = i+1; j < h.size(); j++) {
      |                           ~~^~~~~~~~~~
meetings.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int i = 0; i < l.size(); i++) {
      |                     ~~^~~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 437 ms 504 KB Output is correct
11 Correct 1505 ms 628 KB Output is correct
12 Correct 386 ms 584 KB Output is correct
13 Correct 1205 ms 580 KB Output is correct
14 Correct 88 ms 580 KB Output is correct
15 Correct 270 ms 492 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1650 ms 1836 KB Output is correct
3 Execution timed out 5534 ms 6160 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 204 KB Output is correct
2 Correct 1650 ms 1836 KB Output is correct
3 Execution timed out 5534 ms 6160 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 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 437 ms 504 KB Output is correct
11 Correct 1505 ms 628 KB Output is correct
12 Correct 386 ms 584 KB Output is correct
13 Correct 1205 ms 580 KB Output is correct
14 Correct 88 ms 580 KB Output is correct
15 Correct 270 ms 492 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 1650 ms 1836 KB Output is correct
18 Execution timed out 5534 ms 6160 KB Time limit exceeded
19 Halted 0 ms 0 KB -