Submission #157013

#	Time	Username	Problem	Language	Result	Execution time	Memory
157013		user202729	Cake 3 (JOI19_cake3)	C++17	0 / 100	2 ms	376 KiB

cake3

#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<climits>

struct Myset{
	std::multiset<int> d;
	int64_t sum;

	Myset():d{},sum(0){}

	/* // implementation of some special member function, for safety (after being moved from a set will be in a valid state)
	Myset(Myset const& x)=default;
	Myset(Myset&& x){
		*this=std::move(x);
	}
	Myset& operator=(Myset const& x)=default;
	Myset& operator=(Myset&& x){
		d=std::move(x.d);
		sum=x.sum;
		x.d.clear();
		x.sum=0;
		return *this;
	}
	*/

	int size()const{return d.size();}

	void add(int x){
		sum+=x;
		d.insert(x);
	}

	void del_small(unsigned maxsize){
		while(d.size()>maxsize){
			auto iter=d.begin();
			sum-=*iter;
			d.erase(iter);
		}
	}

	void merge(Myset x){
		sum+=x.sum;
		if(x.d.size()>d.size())
			std::swap(d,x.d);
		for(int z:x.d)
			d.insert(z);
	}

};

int main(){
	std::ios::sync_with_stdio(0);std::cin.tie(0);

	int n,subset_size;std::cin>>n>>subset_size;
	struct Piece{
		int val,depth;
	};
	std::vector<Piece> ps(n);
	for(auto& x:ps)std::cin>>x.val>>x.depth;

	int64_t ans=INT64_MIN;
	{
		std::sort(begin(ps),end(ps),[](Piece a,Piece b){
				return a.depth<b.depth;
				});
		int l=0;
		int r=0;
		int64_t sumval=0;
		while(r<subset_size)
			sumval+=ps[r++].val;
		while(true){
			ans=std::max<int64_t>(ans,sumval-2LL*(ps[r-1].depth-ps[l].depth));
			if(r==n)
				break;
			sumval+=ps[r++].val-ps[l++].val;
		}
	}

	std::sort(begin(ps),end(ps),[](Piece a,Piece b){
			return a.val<b.val;
			});

	std::map<std::pair<int,int>,Myset> m; // {depth1,index} -> set of values with depth > depth1 and < nextdepth
	// (--m.end())->second is empty

	for(int i=0;i<n;++i)
		m.insert({{ps[i].depth,i},{}});
	m.insert({{INT_MIN,-1},{}});

	for(int i=0;i<n;++i){
		std::pair<int,int> depth{ps[i].depth,i};
		auto iter=m.find(depth);
		auto pre=std::prev(iter);

#define key first
#define value second
#define depth_ first
#define index_ second

		Myset lset=std::move(pre->value);
		Myset rset=std::move(iter->value);

		if(lset.size()==subset_size-2)
			ans=std::max<int64_t>(ans,
					lset.sum+ps[pre->key.index_].val+ps[iter->key.index_].val
					-2LL*(iter->key.depth_-pre->key.depth_)
					);
		if(rset.size()==subset_size-2){
			auto nxt=std::next(iter);
			ans=std::max<int64_t>(ans,
					rset.sum+ps[iter->key.index_].val+ps[nxt->key.index_].val
					-2LL*(nxt->key.depth_-iter->key.depth_)
					);
		}

		m.erase(iter);
		if(pre->key.index_>=0){ // ignore values before leftmost non-deleted element
			lset.merge(std::move(rset));
			lset.add(ps[i].val);
			lset.del_small(subset_size-2);
			pre->value=std::move(lset);
		}

#undef key
#undef value
#undef depth_
#undef index_
	}

	std::cout<<ans<<'\n';

}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 19
• Subtask 3: 0 / 76