Submission #598486

#	Time	Username	Problem	Language	Result	Execution time	Memory
598486		imtore	수족관 3 (KOI13_aqua3)	C++14	100 / 100	117 ms	25268 KiB

aqua3

#include <stdio.h>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
#define LL long long
#define pii pair<int, int>
#define ff first
#define ss second
#define INF (int)1e9
using namespace std;

vector<int> X, Y;
priority_queue<LL> pq;

struct Indexed_Tree{
	int bias;
	vector<pii> tree;

	void init(int n){
		for(bias = 1; bias < n; bias <<= 1);
		tree.resize(bias<<1);

		for(int i = 0; i < n; i++) tree[i|bias] = {Y[i+1], i};
		for(int i = n; i < bias; i++) tree[i|bias] = {INF, INF};
		for(int i = bias-1; i; i--) tree[i] = min(tree[i<<1], tree[i<<1|1]);
	}

	pii query_min(int s, int e){
		pii mn = {INF, INF};
		s |= bias; e |= bias;
		while(s <= e){
			if(s&1) mn = min(mn, tree[s++]);
			if(~e&1) mn = min(mn, tree[e--]);
			s >>= 1; e >>= 1;
		}
		return mn;
	}
}IDT;

LL dfs(int s, int e, int y){
	if(s == e) return 0;

	//printf("%d %d %d\n", s, e, y);

	pii mn = IDT.query_min(s, e-1);
	//printf("%d %d\n", mn.ff, mn.ss);
	LL res1 = dfs(s, mn.ss, mn.ff);
	LL res2 = dfs(mn.ss+1, e, mn.ff);
	pq.push(min(res1, res2));
	
	return max(res1, res2)+(LL)(X[e]-X[s])*(mn.ff-y);
}

int main(){
	int n, k;

	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		int x, y; scanf("%d %d", &x, &y);
		X.push_back(x);
		Y.push_back(y);
	}
	scanf("%d", &k);

	X.erase(unique(X.begin(), X.end()), X.end());
	Y.erase(unique(Y.begin(), Y.end()), Y.end());

	//for(int x : X) printf("%d ", x); printf("\n");
	//for(int y : Y) printf("%d ", y); printf("\n");

	IDT.init(X.size()-1);

	//for(int i = 1; i < (IDT.bias<<1); i++) printf("%d : %d %d\n", i, IDT.tree[i].ff, IDT.tree[i].ss);

	pq.push(dfs(0, X.size()-1, 0));

	LL sum = 0;
	for(;!pq.empty() && k--; pq.pop()) sum += pq.top();

	printf("%lld", sum);

	return 0;
}

Compilation message (stderr)

aqua3.cpp: In function 'int main()':
aqua3.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
aqua3.cpp:61:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |   int x, y; scanf("%d %d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~~
aqua3.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |  scanf("%d", &k);
      |  ~~~~~^~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 21 / 21
• Subtask 4: 15 / 15
• Subtask 5: 16 / 16