Submission #782570

#	Time	Username	Problem	Language	Result	Execution time	Memory
782570		qwerasdfzxcl	케이크 (JOI13_cake)	C++17	10 / 100	1564 ms	22812 KiB

cake

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
map<int, ll> mp[300300];
int n, a[300300];

pair<int, int> getL(int l, int r, int typ){
	// naive
	while(a[l] > a[r]){
		l++;
		typ ^= 1;
		if (l>=n) l = 0;
	}

	return {l, typ};
}

pair<int, int> getR(int l, int r, int typ){
	// naive
	while(a[l] < a[r]){
		r--;
		typ ^= 1;
		if (r<0) r = n-1;
	}

	return {r, typ};
}

ll sumL(int l, int r, int typ){
	// naive
	ll ret = 0;
	for (int i=l;;i=(i+1)%n){
		if (typ) ret += a[i];
		typ ^= 1;

		if (i==r) break;
	}

	return ret;
}

ll sumR(int r, int l, int typ){
	// printf("sumR %d %d %d\n", l, r, typ);
	// naive
	ll ret = 0;
	for (int i=r;;i=(n+i-1)%n){
		if (typ) ret += a[i];
		typ ^= 1;

		if (i==l) break;
	}

	// printf(" ok %lld\n", ret);

	return ret;
}

ll dfs(int l, int r, int typ){
	// printf(" call %d %d %d\n", l, r, typ);
	if (l==r) return (typ)?a[l]:0;
	if (mp[l].find(r)!=mp[l].end()) return mp[l][r];
	ll &ret = mp[l][r];

	if (a[l] > a[r]){
		auto [nl, nt] = getL(l, r, typ);
		return ret = sumL(l, (n+nl-1)%n, typ) + dfs(nl, r, nt);
	}

	auto [nr, nt] = getR(l, r, typ);
	return ret = sumR(r, (n+nr+1)%n, typ) + dfs(l, nr, nt);
}

int main(){
	scanf("%d", &n);
	for (int i=0;i<n;i++) scanf("%d", a+i);

	for (int i=0;i<n;i++){
		int l = (n+i+1) % n, r = (n+i-1) % n;
		printf("%lld\n", a[i] + dfs(l, r, 0));
	}
}

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
cake.cpp:76:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |  for (int i=0;i<n;i++) scanf("%d", a+i);
      |                        ~~~~~^~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 90