Submission #807557

#	Time	Username	Problem	Language	Result	Execution time	Memory
807557		Lobo	Meetings (IOI18_meetings)	C++17	19 / 100	5565 ms	753336 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define int long long
const int inf = 1e18+10;

const int maxn = 8e5+10;
int n, a[maxn];
pair<int,int> tr[maxn];
unordered_map<int,int> dp[maxn];

void build(int no, int l, int r) {
	if(l == r) {
		tr[no] = mp(a[l],l);
		return;
	}

	int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	tr[no] = max(tr[lc],tr[rc]);
}

pair<int,int> querymax(int no, int l, int r, int L, int R) {
	if(l > R || r < L) return mp(-inf,0);
	if(l >= L && r <= R) return tr[no];
	int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
	return max(querymax(lc,l,mid,L,R),querymax(rc,mid+1,r,L,R));
}

int sol(int l, int r) {
	if(dp[l].count(r)) return dp[l][r];
	if(l > r) return dp[l][r] = 0;
	int i = querymax(1,1,n,l,r).sc;
	return dp[l][r] = min({(r-l+1)*a[i],sol(l,i-1)+(r-i+1)*a[i],sol(i+1,r)+(i-l+1)*a[i]});
}

vector<long long> minimum_costs(vector<int32_t> H, vector<int32_t> L, vector<int32_t> 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;

  	vector<int> ans;
	n = H.size();
  	for(int i = 1; i <= n; i++) {
  		a[i] = H[i-1];
  	}

  	build(1,1,n);

  	for(int i = 0; i < L.size(); i++) {
  		ans.pb(sol(L[i]+1,R[i]+1));
  	}
  	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:58:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |    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