제출 #418441

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
418441		FlippenFaz	Meetings (IOI18_meetings)	C++11	0 / 100	5597 ms	3760 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 += h[temp] * (min(highestNeighs[temp].second-1, right) - temp+1);
        //cout << "NEW SUM: " << sum << endl;
        temp =  highestNeighs[temp].second;
    }
    temp = mid;
    while (temp >= left) {
        sum += h[temp] * (temp - max(highestNeighs[temp].first+1, left) + 1);
        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]) {
                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;

}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40