Submission #432822

#	Time	Username	Problem	Language	Result	Execution time	Memory
432822		frodakcin	Meetings (IOI18_meetings)	C++11	19 / 100	5552 ms	8312 KiB

meetings

#include "meetings.h"
#include <stack>

template<typename T> bool ckmin(T& a, const T& b) {return b<a?a=b,1:0;}
template<typename T> bool ckmax(T& a, const T& b) {return b>a?a=b,1:0;}

using ll = long long;

const ll INF = 0x3f3f3f3f3f3f3f3f;

ll brute(const std::vector<int>& H, int L, int R)
{
	std::vector<ll> bl, br;
	bl.reserve(R-L), br.reserve(R-L);
	int len = R-L;
	{
		std::stack<int> s; s.push(L-1);
		int ctr=0;
		ll cur=0;
		for(int i=L;i<R;++i)
		{
			cur += H[i];
			for(;s.size()>1 && H[i] > H[s.top()];)
			{
				int pr=s.top();
				s.pop();
				cur += (ll)(pr-s.top())*(H[i]-H[pr]);
			}
			bl.push_back(cur);
			s.push(i);
		}
	}

	{
		std::stack<int> s; s.push(R);
		int ctr=0;
		ll cur=0;
		for(int i=R-1;i>=L;--i)
		{
			cur += H[i];
			for(;s.size()>1 && H[i] > H[s.top()];)
			{
				int pr=s.top();
				s.pop();
				cur += (ll)(s.top()-pr)*(H[i]-H[pr]);
			}
			br.push_back(cur);
			s.push(i);
		}
	}

	ll ans=INF;
	for(int i=0;i<len;++i)
		ckmin(ans, bl[i]+br[len-1-i]-H[L+i]);
	return ans;
}

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

Compilation message (stderr)

meetings.cpp: In function 'll brute(const std::vector<int>&, int, int)':
meetings.cpp:18:7: warning: unused variable 'ctr' [-Wunused-variable]
   18 |   int ctr=0;
      |       ^~~
meetings.cpp:36:7: warning: unused variable 'ctr' [-Wunused-variable]
   36 |   int ctr=0;
      |       ^~~
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:60:6: warning: unused variable 'N' [-Wunused-variable]
   60 |  int N = H.size();
      |      ^

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