Submission #1072574

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072574		pawned	Meetings (IOI18_meetings)	C++17	19 / 100	522 ms	786432 KiB

meetings

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;

#include "meetings.h"

const int MAX = 750005;

vi minimum_costs(vector<int> H_g, vector<int> L_g, vector<int> R_g) {
	int N = H_g.size();
	vi H(N);
	for (int i = 0; i < N; i++) {
		H[i] = H_g[i];
	}
	int Q = L_g.size();
	vector<ii> queries;
	for (int i = 0; i < Q; i++) {
		queries.pb({L_g[i], R_g[i]});
	}
	vector<vi> rm(N, vi(N, 0));	// range maximum on [i, j]
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < i; j++) {
			rm[i][j] = rm[j][i];
		}
		rm[i][i] = H[i];
		for (int j = i + 1; j < N; j++) {
			rm[i][j] = max(rm[i][j - 1], H[j]);
		}
	}
/*	cout<<"rm: "<<endl;
	for (vi v : rm) {
		for (int x : v)
			cout<<x<<" ";
		cout<<endl;
	}*/
	vector<vi> rms(N, vi(N + 1, 0));
	for (int i = 0; i < N; i++) {
		for (int j = 1; j <= N; j++) {
			rms[i][j] = rms[i][j - 1] + rm[i][j - 1];
		}
	}
	vi ans(Q);
	for (int i = 0; i < Q; i++) {
		int L = queries[i].fi;
		int R = queries[i].se;
		ll minimum = 1e18;
		for (int j = L; j <= R; j++) {	// this is center
			ll total = rms[j][R + 1] - rms[j][L];
			minimum = min(minimum, total);
		}
//		cout<<"ANSWER: ";
//		cout<<minimum<<endl;
		ans[i] = minimum;
	}
	return ans;
}

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