Submission #596147

#	Time	Username	Problem	Language	Result	Execution time	Memory
596147		FatihSolak	Meetings (IOI18_meetings)	C++17	19 / 100	552 ms	3664 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define N 5005
using namespace std;
long long cost[N];
vector<long long> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
	int q = l.size();
	int n = h.size();
	vector<long long> res(q);
	for(int i = 0;i<q;i++){
		long long ans = 1e18;
		for(int j = l[i];j<=r[i];j++){
			cost[j] = -h[j];
		}
		long long now = 0;
		vector<int> st;
		for(int j = l[i];j<=r[i];j++){
			while(st.size() && h[j] >= h[st.back()]){
				int rem = st.back();
				st.pop_back();
				int x = l[i];
				if(st.size())
					x = st.back() + 1;
				now -= (long long)h[rem] * (rem - x + 1);
			}
			int x = l[i];
			if(st.size())
				x = st.back() + 1;	
			now += (long long)h[j] * (j - x + 1);
			st.push_back(j);
			cost[j] += now;
		}
		st.clear();
		now = 0;
		for(int j = r[i];j>=l[i];j--){
			while(st.size() && h[j] >= h[st.back()]){
				int rem = st.back();
				st.pop_back();
				int x = r[i];
				if(st.size())
					x = st.back() - 1;
				now -= (long long)h[rem] * (x - rem + 1);
			}
			int x = r[i];
			if(st.size())
				x = st.back() - 1;	
			now += (long long)h[j] * (x - j + 1);
			st.push_back(j);
			cost[j] += now;
		}
		for(int j = l[i];j<=r[i];j++){
			ans = min(ans,cost[j]);
		}
		res[i] = ans;
	}
	return res;
}

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:8:6: warning: unused variable 'n' [-Wunused-variable]
    8 |  int n = h.size();
      |      ^

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