Submission #338301

#	Time	Username	Problem	Language	Result	Execution time	Memory
338301		alishahali1382	Candies (JOI18_candies)	C++14	100 / 100	449 ms	173384 KiB

candies

#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define SZ(x) ((int)x.size())

const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=200010, LOG=20;
typedef vector<ll> DP;

int n, m, k, u, v, x, y, t, a, b, ans;
int A[MAXN];
DP vec[MAXN<<2][2][2], v1, v2;

inline void Add(DP &vec, int x){
	vec.pb(-INF);
	for (int i=SZ(vec)-1; i; i--) vec[i]=max(vec[i], vec[i-1]+x);
}
inline void Merge(DP &X, DP &Y, DP &Z){
//	debugv(X)
//	debugv(Y)
	
	int i=0, j=0;
	Z={0};
	Z.resize(SZ(X)+SZ(Y)-1, -INF);
	for (int k=1; k<SZ(Z); k++){
		int tmp=0;
		if (i+1<SZ(X) && X[i+1]+Y[j]>Z[k]) Z[k]=X[i+1]+Y[j], tmp=1;
		if (j+1<SZ(Y) && X[i]+Y[j+1]>Z[k]) Z[k]=X[i]+Y[j+1], tmp=2;
		if (tmp==1) i++;
		else j++;
	}
//	debugv(Z)
//	cerr<<"\n";
}
void divide(int id, int tl, int tr){
//	debug2(tl, tr)
	if (tr-tl==1){
		vec[id][0][0]={0, A[tl]};
		vec[id][0][1]=vec[id][1][0]=vec[id][1][1]={0};
		return ;
	}
	if (tr-tl==2){
		vec[id][0][0]={0, max(A[tl], A[tl+1])};
		vec[id][0][1]={0, A[tl]};
		vec[id][1][0]={0, A[tl+1]};
		vec[id][1][1]={0};
		return ;
	}
	int mid=(tl+tr)>>1;
	divide(id<<1, tl, mid);
	divide(id<<1 | 1, mid, tr);
//	debug2(tl, tr)
	for (int i:{0, 1}) for (int j:{0, 1}){
//		debug2(i, j)
//		debugv(vec[id<<1][0][0])
//		debugv(vec[id<<1 | 1][1][0])
		
		Merge(vec[id<<1][i][0], vec[id<<1 | 1][1][j], v1);
		Merge(vec[id<<1][i][1], vec[id<<1 | 1][0][j], v2);
//		debug("shit")
		if (SZ(v1)>SZ(v2)) v2.pb(-INF);
		if (SZ(v1)<SZ(v2)) v1.pb(-INF);
		for (int k=0; k<SZ(v1); k++) vec[id][i][j].pb(max(v1[k], v2[k]));
//		debug("fuck")
		
	}
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n;
	for (int i=1; i<=n; i++) cin>>A[i];
	divide(1, 1, n+1);
	for (int i=1; i<=(n+1)/2; i++) cout<<vec[1][0][0][i]<<"\n";
	
	return 0;
}
/*
5
3 5 1 7 6

*/

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