oj.uz

Submission #782570

# Submission time Handle Problem Language Result Execution time Memory
782570 2023-07-14T05:36:58 Z qwerasdfzxcl 케이크 (JOI13_cake) C++17
10 / 100
 1500 ms 22812 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15188 KB Output is correct
2 Correct 144 ms 15036 KB Output is correct
3 Correct 50 ms 15248 KB Output is correct
4 Correct 13 ms 15188 KB Output is correct
5 Correct 142 ms 15036 KB Output is correct
6 Correct 64 ms 15264 KB Output is correct
7 Correct 25 ms 15048 KB Output is correct
8 Correct 39 ms 15140 KB Output is correct
9 Correct 7 ms 14416 KB Output is correct
10 Correct 8 ms 14292 KB Output is correct
11 Correct 7 ms 14420 KB Output is correct

Subtask #2
0 / 90.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1564 ms 22812 KB Time limit exceeded
2 Halted 0 ms 0 KB -