Submission #85097

#	Time	Username	Problem	Language	Result	Execution time	Memory
85097		SirCeness	Meetings (IOI18_meetings)	C++14	4 / 100	5585 ms	3384 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

map<long long, long long> m;

long long get(vector<int> H, int l, int r){
	//cout << "get(" << l << ", " << r << ")" << endl;
	if (m.find(l*750000 + r) != m.end()) return m.find(l*750000+r) -> second;
	if (l == r) return H[l];
	if (l > r) return 0;
	int size = r-l+1;
	long long maxx = 0;
	for (int i = l; i <= r; i++){
		if (maxx < H[i]) maxx = H[i];
	}
	vector<long long> maxs;
	for (int i = l; i <= r; i++){
		if (H[i] == maxx) maxs.push_back(i);
	}
	
	long long min = get(H, l, maxs[0]-1) + maxx*(size - maxs[0] + l);
	for (int i = 1; i < maxs.size(); i++){
		long long a = get(H, maxs[i-1]+1, maxs[i]-1) + maxx*(size - maxs[i] + maxs[i-1] + 1);
		if (a < min) min = a;
	}
	long long a = get(H, maxs[maxs.size()-1]+1, r) + maxx*(size - (r - (maxs[maxs.size()-1]+1) + 1));
	if (a < min) min = a;
	m.insert(make_pair(l*750000+r, min));
	return min;
	
}

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
	//cout << "basla" << endl;
	
	int Q = L.size();
	vector<long long> ret(Q);
	
	for (int i = 0; i < Q; i++){
		ret[i] = get(H, L[i], R[i]);
	}
	
	return ret;
}

/*
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
  int Q = L.size();
  std::vector<long long> C(Q);
  for (int j = 0; j < Q; ++j) {
    C[j] = H[L[j]];
  }
  return C;
}
*/

Compilation message (stderr)

meetings.cpp: In function 'long long int get(std::vector<int>, int, int)':
meetings.cpp:24:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < maxs.size(); i++){
                  ~~^~~~~~~~~~~~~

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