Submission #159859

#	Time	Username	Problem	Language	Result	Execution time	Memory
159859		qkxwsm	Meetings (IOI18_meetings)	C++14	19 / 100	1279 ms	396340 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define MAXN 131313
#define LLINF 2696969696969696969

typedef long long ll;
typedef double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, Q;
ll arr[MAXN];
pii query[MAXN];
vpi queries[MAXN];
ll mx[5013][5013], pmx[5013][5013];
int dp[MAXN];
vl ans;



vl minimum_costs(vi h, vi l, vi r)
{
	N = SZ(h); Q = SZ(r); ans.resize(Q);
	FOR(i, 0, N)
	{
		arr[i] = h[i];
	}
	FOR(i, 0, Q)
	{
		query[i] = {l[i], r[i]};
	}
	if (N <= 5013 && Q <= 5013)
	{
		FOR(i, 0, N)
		{
			mx[i][i] = arr[i];
			FOR(j, i + 1, N)
			{
				mx[i][j] = max(mx[i][j - 1], arr[j]);
				mx[j][i] = mx[i][j];
			}
		}
		FOR(i, 0, N)
		{
			FOR(j, 0, N)
			{
				pmx[i][j + 1] = pmx[i][j] + mx[i][j];
			}
		}
		FOR(i, 0, Q)
		{
			int l = query[i].fi, r = query[i].se;
			ans[i] = LLINF;
			FOR(j, l, r + 1)
			{
				ckmin(ans[i], pmx[j][r + 1] - pmx[j][l]);
			}
		}
	}
	// level 0: must be <= 20, co = 0.
	// level 1: must be <= 19, co = 1.
	// ...
	// level 18: must be <= 2, co = 18.
	// level 19: must be <= 1, co = 19.
	// level 20: must be <= 2, sum = 18.
	// ...
	// level 37: must be <= 19, sum = 1.
	// level 38: must be <= 20, sum = 0.
	return ans;
}

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