Submission #100784

#	Time	Username	Problem	Language	Result	Execution time	Memory
100784		JPN20	Candies (JOI18_candies)	C++17	100 / 100	4102 ms	18856 KiB

candies

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

struct Node{
	vector<long long> p[4];
};

vector<long long> check(vector<long long>A, vector<long long>B) {
	vector<long long>ans;
	
	int cnt = 3, L = 2; while (L < (int)(A.size() + B.size())) { L *= 3; L /= 2; cnt++; }
	
	int maxs = A.size() - 1 + B.size() - 1;
	for (int i = 0; i <= maxs; i++) {
		int L = 0, R = A.size(), c1, c2;
		if (i >= (int)B.size()) L = i - ((int)B.size() - 1);
		if (i < (int)A.size()) R = i + 1;
		
		int cl = L, cr = R;
		
		for (int j = 0; j < cnt; j++) {
			c1 = (L + L + R) / 3;
			c2 = (L + R + R) / 3;
			long long E1 = A[c1] + B[i - c1];
			long long E2 = A[c2] + B[i - c2];
			if (E1 < E2) L = c1;
			else R = c2;
		}
		
		long long rets = 0;
		for (int j = -3; j <= 3; j++) {
			int ss = c1 + j; if (ss < cl || cr <= ss) continue;
			rets = max(rets, A[ss] + B[i - ss]);
		}
		ans.push_back(rets);
	}
	return ans;
}

Node calc(Node A1, Node A2) {
	// i = 1 or 3 : 一番後ろに飴がある
	// i = 2 or 3 : 一番前に飴がある
	Node E;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			if ((i == 1 || i == 3) && (j == 2 || j == 3)) continue;
			vector<long long> I = check(A1.p[i], A2.p[j]);
			
			int ty = 0; if (i == 2 || i == 3) ty += 2; if (j == 1 || j == 3) ty += 1;
			for (int j = 0; j < (int)I.size(); j++) {
				if ((int)E.p[ty].size() == j) E.p[ty].push_back(I[j]);
				else E.p[ty][j] = max(E.p[ty][j], I[j]);
			}
		}
	}
	return E;
}

long long N, A[200009], C[200009];

Node solve(int l, int r) {
	if (l + 1 == r) {
		Node I;
		I.p[0] = {0};
		I.p[1] = {0};
		I.p[2] = {0};
		I.p[3] = {0, A[l]};
		return I;
	}
	
	Node LL = solve(l, (l + r) / 2);
	Node RR = solve((l + r) / 2, r);
	return calc(LL, RR);
}

int main() {
	scanf("%lld", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%lld", &A[i]);
	}
	
	Node T = solve(1, N + 1);
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < T.p[i].size(); j++) C[j] = max(C[j], T.p[i][j]);
	}
	
	for (int i = 1; i <= (N + 1) / 2; i++) printf("%lld\n", C[i]);
	return 0;
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:84:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < T.p[i].size(); j++) C[j] = max(C[j], T.p[i][j]);
                   ~~^~~~~~~~~~~~~~~
candies.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &N);
  ~~~~~^~~~~~~~~~~~
candies.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &A[i]);
   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92