Submission #678235

#	Time	Username	Problem	Language	Result	Execution time	Memory
678235		arnold518	Seesaw (JOI22_seesaw)	C++17	0 / 100	1 ms	260 KiB

seesaw

#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 2e5;

int N, A[MAXN+10];
ll S[MAXN+10];

bool cmp (pii p, pii q)
{
	p.first--; q.first--;
	return (__int128)(S[p.second]-S[p.first])*(q.second-q.first) <= (__int128)(S[q.second]-S[q.first])*(p.second-p.first);
}

double ans=1e18;

int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%d", &A[i]), S[i]=S[i-1]+A[i];

	pii p(1, N), q(1, N);
	while(p.first<p.second)
	{
		if(cmp(pii(p.first+1, p.second), pii(1, N))) p.first++;
		else p.second--;
		if(cmp(p, q)) q=p;
		//printf("%d %d\n", p.first, p.second);
	}
	ans=min(ans, (double)S[N]/N-(double)(S[q.second]-S[q.first-1])/(q.second-q.first+1));

	p=pii(1, N), q=pii(1, N);
	while(p.first<p.second)
	{
		if(cmp(pii(1, N), pii(p.first, p.second-1))) p.second--;
		else p.first++;
		if(cmp(q, p)) q=p;
	}
	ans=min(ans, (double)(S[q.second]-S[q.first-1])/(q.second-q.first+1)-(double)S[N]/N);

	printf("%.20lf\n", ans);
}

Compilation message (stderr)

seesaw.cpp: In function 'int main()':
seesaw.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
seesaw.cpp:24:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |  for(int i=1; i<=N; i++) scanf("%d", &A[i]), S[i]=S[i-1]+A[i];
      |                          ~~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 1
• Subtask 2: 0 / 33
• Subtask 3: 0 / 33
• Subtask 4: 0 / 33