oj.uz

Submission #127007

# Submission time Handle Problem Language Result Execution time Memory
127007 2019-07-08T19:13:00 Z Lawliet Sure Bet (CEOI17_sure) C++14
60 / 100
 5 ms 376 KB 
#include <bits/stdc++.h>
 
#define MAX 1010
 
using namespace std;
 
int n;
 
double ans = -4000000.0;
 
double a[MAX];
double b[MAX];
double ansA[MAX];
double ansB[MAX];
double mxAnsB[MAX];

bool test(double k)
{
	for(int qtdA = 0 ; qtdA <= n ; qtdA++)
	{
		double aux = ansA[qtdA] - k;

		//printf("===== qtdA = %d      %lf\n",qtdA,aux);

		if(ansA[qtdA] < k) continue;

		int mxQtdB = floor( aux );
		mxQtdB = min(mxQtdB , n);

		//printf("----------------- qtdA = %d        mxQtdB = %d\n",qtdA,mxQtdB);

		if(mxAnsB[ mxQtdB ] - qtdA >= k) return true;
	}

	return false;
}

double bs()
{
	double l = 0, r = 200000000.0;

	for(int cnt = 0 ; cnt <= 500 ; cnt++)
	{
		double m = (l + r)/2;

		//printf("l = %lf  r = %lf  m = %lf\n",l,r,m);

		if(test(m)) l = m;
		else r = m;
	}

	return l;
}

void init()
{
	sort(a + 1 , a + n + 1);
	sort(b + 1 , b + n + 1);

	for(int g = 1 ; g <= n ; g++)
	{
		ansA[g] = ansA[g - 1] + a[n - g + 1];
		ansB[g] = ansB[g - 1] + b[n - g + 1];

		//printf("g = %d        ansA = %lf\n",g,ansA[g]);
	}

	for(int g = 1 ; g <= n ; g++)
	{
		ansA[g] -= g;
		ansB[g] -= g;

		mxAnsB[g] = max(mxAnsB[g - 1] , ansB[g]);
	}


}
 
int main()
{
	scanf("%d",&n);
 
	for(int g = 1 ; g <= n ; g++)
		scanf("%lf %lf",&a[g],&b[g]);
 
	init();
 
	printf("%.4lf\n",bs());
}

Compilation message

sure.cpp: In function 'int main()':
sure.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
sure.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lf %lf",&a[g],&b[g]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 4 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 4 ms 376 KB Output is correct
15 Correct 4 ms 376 KB Output is correct
16 Correct 3 ms 376 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 4 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 4 ms 376 KB Output is correct
15 Correct 4 ms 376 KB Output is correct
16 Correct 3 ms 376 KB Output is correct
17 Execution timed out 3 ms 376 KB Time limit exceeded (wall clock)
18 Halted 0 ms 0 KB -