Submission #221831

#	Time	Username	Problem	Language	Result	Execution time	Memory
221831		patrikpavic2	Candies (JOI18_candies)	C++17	0 / 100	5 ms	512 KiB

candies

#include <cstdio>
#include <vector>
#include <algorithm>

#define PB push_back
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair < int, int > pii;

const int N = 2e5 + 500;

int un[N], n;
int L[N], R[N], par[N], uk = 0, A[N];
ll pref[N][2], kol[N], sol, ans[N];
vector < pair < int, int > > v;

ll get(int l,int r,int k){
	return pref[r][k] - (l ? pref[l - 1][k] : 0);
}

int pr(int x){
	if(x == par[x]) return x;
	return par[x] = pr(par[x]);
}

void mrg(int x,int y){
	//printf("spajam %d i %d\n", x, y);
	x = pr(x), y = pr(y);
	if(R[y] - L[y] > R[x] - L[x]) 
		swap(x, y);
	uk -= (R[x] - L[x] + 2) / 2, sol -= kol[x];
	uk -= (R[y] - L[y] + 2) / 2, sol -= kol[y];
	par[y] = x;
	L[x] = min(L[x], L[y]);
	R[x] = max(R[x], R[y]);
	if((R[x] - L[x] + 1) & 1)
		kol[x] = get(L[x], R[x], L[x] & 1);
	else
		kol[x] = max(get(L[x], R[x], 0), get(L[x], R[x], 1));
	uk += (R[x] - L[x] + 2) / 2;
	sol += kol[x];
	//printf("kol[ %d ] = %lld sol = %lld uk = %d\n", x, kol[x], sol, uk);
}


int main(){
	scanf("%d", &n);
	for(int i = 0;i < n;i++){
		par[i] = i; L[i] = i; R[i] = i;
		scanf("%d", A + i); 
		pref[i][i&1] = A[i]; 
		v.PB({A[i], i});
	}
	for(int i = 1;i < n;i++)
		pref[i][0] += pref[i - 1][0],
		pref[i][1] += pref[i - 1][1];
	sort(v.rbegin(), v.rend());
	for(int j = 0;j < n;j++){
		int i = v[j].Y; un[i] = 1;
		uk++; kol[i] = A[i]; sol += kol[i];
		if(i && un[i - 1]) mrg(i - 1, i);
		if(un[i + 1]) 	   mrg(i + 1, i);
	    ans[uk] = max(ans[uk], sol);
	}
	for(int i = 1;i <= (n + 1) / 2;i++)
		printf("%lld\n", ans[i]);
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
candies.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", A + i); 
   ~~~~~^~~~~~~~~~~~~

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