Submission #135657

#	Time	Username	Problem	Language	Result	Execution time	Memory
135657		E869120	Cake 3 (JOI19_cake3)	C++14	0 / 100	3 ms	376 KiB

cake3

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

class SegmentTree {
public:
	vector<pair<long long, int>> val;

	void add(pair<long long, int>x) {
		val.push_back(x);
		sort(val.begin(), val.end());
	}
	void lose(pair<long long, int>x) {
		vector<pair<long long, int>> val2;
		for (int i = 0; i < val.size(); i++) {
			if (val[i] == x) continue;
			val2.push_back(val[i]);
		}
		val = val2;
	}
	long long getmax(long long M) {
		if (val.size() < M) return -(1LL << 60);
		long long sum = 0;
		for (int i = (int)val.size() - 1; i >= (int)val.size() - M; i--) sum += val[i].first;
		return sum;
	}
};

long long N, M, C[1 << 18], V[1 << 18], ans[1 << 18], id[1 << 18], SIZE_ = 1;
vector<pair<long long, long long>>A;

int main() {
	// --------------------------- 入力・ソート ----------------------
	scanf("%lld%lld", &N, &M);
	for (int i = 0; i < N; i++) {
		scanf("%lld%lld", &V[i], &C[i]);
		A.push_back(make_pair(C[i], V[i]));
	}
	sort(A.begin(), A.end());
	for (int i = 1; i <= N; i++) {
		C[i] = A[i - 1].first; V[i] = A[i - 1].second;
	}

	// ---------------------------- ただの分割 -----------------------
	while (SIZE_ <= N) SIZE_ *= 2;
	ans[SIZE_] = -(1LL << 60); id[SIZE_] = N;
	ans[0] = -(1LL << 60); id[0] = 1;

	for (int i = (SIZE_ >> 1); i >= 1; i >>= 1) {
		vector<int> vec;
		for (int j = i; j < SIZE_; j += i * 2) vec.push_back(j);

		SegmentTree Z;

		int cx = N;
		for (int j = vec.size() - 1; j >= 0; j--) {
			// 新たに追加する
			for (int k = vec[j]; k < min((int)id[vec[j] + i] + 1, cx); k++) {
				if (k <= N) Z.add(make_pair(V[k], k));
			}

			// 答えを求める
			pair<long long, int> maxid = make_pair(-(1LL << 59), N);
			for (int k = id[vec[j] + i]; k >= id[vec[j] - i]; k--) {
				long long v = Z.getmax(M) - 2LL * (C[k] - C[vec[j]]);
				maxid = max(maxid, make_pair(v, k));
				if (k >= vec[j] && k != id[vec[j] - i]) {
					Z.lose(make_pair(V[k], k));
				}
			}
			ans[vec[j]] = maxid.first;
			id[vec[j]] = maxid.second;

			cx = vec[j];
		}
	}

	// --------------------------- 答えを求める ----------------------
	long long FinalAns = -(1LL << 60);
	for (int i = 1; i <= N; i++) FinalAns = max(FinalAns, ans[i]);
	cout << FinalAns << endl;
	return 0;
}

Compilation message (stderr)

cake3.cpp:5:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
cake3.cpp: In member function 'void SegmentTree::lose(std::pair<long long int, int>)':
cake3.cpp:17:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < val.size(); i++) {
                   ~~^~~~~~~~~~~~
cake3.cpp: In member function 'long long int SegmentTree::getmax(long long int)':
cake3.cpp:24:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (val.size() < M) return -(1LL << 60);
       ~~~~~~~~~~~^~~
cake3.cpp: In function 'int main()':
cake3.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~~~~~
cake3.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &V[i], &C[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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