oj.uz

Submission #100782

# Submission time Handle Problem Language Result Execution time Memory
100782 2019-03-14T10:45:22 Z JPN20 Candies (JOI18_candies) C++17
0 / 100
 49 ms 504 KB 
#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 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 < 30; j++) {
			c1 = (L + L + R) / 3;
			c2 = (L + R + R) / 3;
			long long E1 = A[c1] + B[i - c1];
			long long E2 = B[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

candies.cpp: In function 'int main()':
candies.cpp:79: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:75:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &N);
  ~~~~~^~~~~~~~~~~~
candies.cpp:76:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= N; i++) scanf("%lld", &A[i]);
                               ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -