Submission #678235

# Submission time Handle Problem Language Result Execution time Memory
678235 2023-01-05T10:36:17 Z arnold518 Seesaw (JOI22_seesaw) C++17
0 / 100
1 ms 260 KB
#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

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];
      |                          ~~~~~^~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 260 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 260 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 260 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 260 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -