제출 #132573

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
132573		dvdg6566	모임들 (IOI18_meetings)	C++14	19 / 100	252 ms	198116 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef vector<ll> vi;
typedef vector<pi> vpi;
#define mp make_pair
#define pb emplace_back
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (ll)x.size()

ll A[5010];

struct SparseTable{
	ll N,K;
	vector<vpi> ST;
	SparseTable(ll _N){
		N=_N;K=MSB(N);
		ST.resize(K);
		for (ll i=0;i<N;++i)ST[0].pb(mp(i,A[i]));
		for (ll k=1;k<K;++k){
			for (ll i=0;i+(1<<k)<=N;++i){
				if (ST[k-1][i].s > ST[k-1][i+(1<<(k-1))].s){
					ST[k].pb(ST[k-1][i]);
				}
				else ST[k].pb(ST[k-1][i+(1<<(k-1))]);
			}
		}
	}
	inline int MSB(unsigned int x){return 32-__builtin_clz(x);}
	pi query(ll x, ll y){
		ll k = MSB(y-x+1)-1;
		if (ST[k][x].s > ST[k][y-(1<<k)+1].s)return ST[k][x];
		return ST[k][y-(1<<k)+1];
	}
}*S;

ll memo[5010][5010];

ll ask(ll x, ll y){
	if (memo[x][y] != -1)return memo[x][y];
	if (x==y)return memo[x][y] = A[x];
	pi tall = S->query(x,y);
	// cout<<"Tall "<<tall.f<<' '<<tall.s<<'\n';
	// Answer is on one side of tall
	if (tall.f == x){
		return memo[x][y] = A[x] + ask(x+1,y);
	}
	if (tall.f == y){
		return memo[x][y] = A[y] + ask(x,y-1);
	}
	ll l = ask(x,tall.f-1);
	ll r = ask(tall.f+1,y);
	ll ld = tall.f-x+1;
	ll rd = y-tall.f+1;
	return memo[x][y] = min(ld*tall.s+r, rd*tall.s+l);
}

ll N,Q;

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
  N = SZ(H);
  Q = SZ(L);
  std::vector<long long> C(Q);
  for (ll j = 0; j < Q; ++j) {
    C[j] = -1;
  }
  if (Q <= 5000){
  	for (ll i=0;i<N;++i)A[i]=H[i];
  	S = new SparseTable(N);
  	memset(memo,-1,sizeof(memo));
  	for (ll i=0;i<Q;++i){
  		C[i] = ask(L[i],R[i]);
  	}
  }
  return C;
}

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