제출 #741672

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
741672		myrcella	모임들 (IOI18_meetings)	C++17	19 / 100	907 ms	3028 KiB

meetings

//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

//#include "meetings.h"

const int maxn = 5050;
ll pre[maxn],suf[maxn];

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
  int Q = L.size();
  std::vector<long long> C(Q);
  rep(_,0,Q) {
	  int l = L[_],r = R[_];
	  pre[l] = H[l];
	  stack <pii> s;
	  s.push({mod,l-1});
	  s.push({H[l],l});
	  ll sum;
	  pre[l] = sum = H[l];
	  rep(i,l+1,r+1) {
		  while (s.top().fi<=H[i]) {
			  int val = s.top().fi,pos = s.top().se;
			  s.pop();
			  sum -= 1ll*val*(pos - s.top().se);
		  }
		  sum += 1ll*H[i]*(i-s.top().se);
		  s.push({H[i],i});
		  pre[i] = sum;
	  }
	  while (!s.empty()) s.pop();
	  suf[r] = H[r];
	  s.push({mod,r+1});
	  s.push({H[r],r});
	  suf[r] = sum = H[r];
	  for (int i = r-1;i>=l;i--) {
		  while (s.top().fi<=H[i]) {
			  int val = s.top().fi,pos = s.top().se;
			  s.pop();
			  sum -= 1ll*val*(s.top().se - pos);
		  }
		  sum += 1ll*H[i]*(s.top().se-i);
		  s.push({H[i],i});
		  suf[i] = sum;
	  }
	  ll ans = 1e18;
	  rep(i,l,r+1) ans =  min(ans,pre[i] + suf[i] - (ll)H[i]);
	  C[_] = ans; 
  }
  return C;
}

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