Submission #145661

#	Time	Username	Problem	Language	Result	Execution time	Memory
145661		Minnakhmetov	Meetings (IOI18_meetings)	C++14	0 / 100	1096 ms	684060 KiB

meetings

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

#define ll long long
#define all(aaa) aaa.begin(), aaa.end()

const ll INF = 1e18;
const int N = 5005;
int dp[N][N], opt[N][N];
ll lp[N][N], rp[N][N];

std::vector<long long> minimum_costs(std::vector<int> a, std::vector<int> L,
                                     std::vector<int> R) {
  	int n = a.size(), q = L.size();

  	for (int i = 0; i < n; i++) {
  		ll cur = 0;
  		int mx = a[i];
  		for (int j = i - 1; j >= 0; j--) {
  			mx = max(mx, a[j]);
  			cur += mx;
  			lp[j][i] = cur;
  		}

  		cur = 0;
  		mx = a[i];

  		for (int j = i + 1; j < n; j++) {
  			mx = max(mx, a[j]);
  			cur += mx;
  			rp[i][j] = cur;
  		}

  		dp[i][i] = a[i];
  		opt[i][i] = i;
  	}

  	// cout << rp[0][2] << "\n";
  	// return vector<ll>(q, 0);

  	for (int i = n - 1; i >= 0; i--) {
  		for (int j = i + 1; j < n; j++) {
  			ll val = INF;
  			int x = -1;

  			for (int k = opt[i][j - 1]; k <= opt[i + 1][j]; k++) {
  				ll cur = lp[i][k] + rp[k][j] + a[k];
  				if (cur < val) {
  					val = cur;
  					x = k;
  				}
  			}

  			opt[i][j] = x;
  			dp[i][j] = val;
  		}
  	}

  	vector<ll> ans(q);

  	for (int i = 0; i < q; i++) {
  		ans[i] = dp[L[i]][R[i]];
  	}

  	return ans;
}

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