Submission #418606

#	Time	Username	Problem	Language	Result	Execution time	Memory
418606		FlippenFaz	모임들 (IOI18_meetings)	C++11	19 / 100	5534 ms	6160 KiB

meetings

#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 (stderr)

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 / 4
• Subtask 2: 15 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40