Submission #200069

#	Time	Username	Problem	Language	Result	Execution time	Memory
200069		dennisstar	Candies (JOI18_candies)	C++17	0 / 100	19 ms	9848 KiB

candies

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = (1ll<<60);

const int SZ = 500;
int N, M, sz[1005];
ll A[200010], x[100010], o[100010], B[1005][SZ+5];
ll XX[SZ+5][SZ+5], XO[SZ+5][SZ+5], OX[SZ+5][SZ+5], OO[SZ+5][SZ+5];

void f(int t) {
	fill(OX[1], OX[1]+SZ+1, -INF); fill(XX[1], XX[1]+SZ+1, -INF); fill(OO[1], OO[1]+SZ+1, -INF); fill(XO[1], XO[1]+SZ+1, -INF);
	XX[1][0]=XO[1][1]=0; OX[1][1]=OO[1][1]=B[t][1];
	for (int i=2; i<=sz[t]; i++) {
		fill(OX[i], OX[i]+SZ+1, -INF); fill(XX[i]+1, XX[i]+SZ+1, -INF); fill(OO[i], OO[i]+SZ+1, -INF); fill(XO[i], XO[i]+SZ+1, -INF);
		for (int j=(i+1)/2; j; j--) XX[i][j]=max(XO[i-1][j], XX[i-1][j]);
		for (int j=(i+1)/2; j; j--) XO[i][j]=XX[i-1][j-1]+B[t][i];
		for (int j=(i+1)/2; j; j--) OX[i][j]=max(OO[i-1][j], OX[i-1][j]);
		for (int j=(i+1)/2; j>=2; j--) OO[i][j]=OX[i-1][j-1]+B[t][i];
	}
}

int main() {
	scanf("%d", &N); M=(N+SZ-1)/SZ;
	for (int i=0; i<N; i++) scanf("%d", &A[i]), B[i/SZ][i%SZ+1]=A[i], sz[i/SZ]++;
	fill(x+1, x+100001, -INF); fill(o+1, o+100001, -INF);
	for (int i=0; i<M; i++) {
		f(i);
		for (int j=(N+1)/2; j>=0; j--) {
			for (int k=min(j, (sz[i]+1)/2); k>=0; k--) x[j]=max({x[j], o[j], XX[sz[i]][k]+max(x[j-k], o[j-k]), OX[sz[i]][k]+x[j-k]});
			for (int k=min(j, (sz[i]+1)/2); k; k--) o[j]=max({o[j], XO[sz[i]][k]+max(x[j-k], o[j-k]), OO[sz[i]][k]+x[j-k]});
		}
	}
	for (int i=1; i<=(N+1)/2; i++) printf("%lld\n", max(x[i], o[i]));
	return 0;
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:25:43: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll* {aka long long int*}' [-Wformat=]
  for (int i=0; i<N; i++) scanf("%d", &A[i]), B[i/SZ][i%SZ+1]=A[i], sz[i/SZ]++;
                                      ~~~~~^
candies.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N); M=(N+SZ-1)/SZ;
  ~~~~~^~~~~~~~~~
candies.cpp:25:66: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=0; i<N; i++) scanf("%d", &A[i]), B[i/SZ][i%SZ+1]=A[i], sz[i/SZ]++;
                          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

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