제출 #858801

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

meetings

#ifndef LOCAL
#include "meetings.h"
#endif
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define inf 1000000000000000000ll
using namespace std;
typedef long long ll;

vector<ll> minimum_costs(vector<int> h, vector<int> l, vector<int> p){
	int n = h.size();
	int q = l.size();
	vector maks(n, vector(n, 0));
	REP(i, n){
		maks[i][i] = h[i];
		FOR(j, i+1, n-1) maks[i][j] = max(maks[i][j-1], h[j]);
	}
	vector doprawej(n, vector(n, 0ll));
	vector dolewej(n, vector(n, 0ll));
	REP(i, n){
		doprawej[i][i] = dolewej[i][i] = h[i];
		FOR(j, i+1, n-1) dolewej[i][j] = dolewej[i][j-1]+maks[i][j];
		for(int j = i; ~--j;) doprawej[j][i] = doprawej[j+1][i]+maks[j][i];
	}
	
	vector<ll> ret(q);
	REP(nr, q){
		int a = l[nr], b = p[nr];
		ret[nr] = inf;
		FOR(i, a, b) ret[nr] = min(ret[nr], doprawej[a][i]+dolewej[i][b]-h[i]);
	}
	return ret;
}
#ifdef LOCAL
int main(){
	int n, q;
	scanf("%d%d", &n, &q);
	vector<int> h(n);
	REP(i, n) scanf("%d", &h[i]);
	vector<int> l(q), p(q);
	REP(i, q) scanf("%d%d", &l[i], &p[i]);
	vector<ll> ret = minimum_costs(h, l, p);
	for(ll x : ret) printf("%lld\n", x);
	return 0;
}
#endif

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