oj.uz

Submission #121197

# Submission time Handle Problem Language Result Execution time Memory
121197 2019-06-26T07:55:52 Z claudy Sure Bet (CEOI17_sure) C++14
100 / 100
 158 ms 10744 KB 
//# pragma GCC optimize("Ofast,no-stack-protector")
//# pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
# pragma GCC optimize("Ofast")
# pragma GCC optimization ("unroll-loops")
# include "bits/stdc++.h"
std::pair<int,int> DR[] = {{-1,0},{0,1},{1,0},{0,-1},{-1,1},{-1,-1},{1,1},{1,-1}};
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define rcg(s) cout << s;exit(0)
# define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
# define db(x) cerr << #x << " = " << x << '\n'
# define pb push_back
# define mp make_pair
# define all(s) s.begin(),s.end()
# define sz(x) (int)((x).size())
//# define int ll
using namespace std;

// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# define LOCAL
# define sim template < class c
# define ris return * this
# define dor > debug & operator <<
# define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define show(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
int gcd(int a, int b)
{
if(b) return gcd(b,a%b);
return a;
}mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

int n;
vector<long double>veca,vecb;
long double a[1 << 17],b[1 << 17];
vector<long double>vals;

int32_t main(){_
	//freopen("input","r",stdin);
	cin >> n;
	for(int i = 1;i <= n;i++)
	{
		long double x,y;
		cin >> x >> y;
		veca.pb(x);
		vecb.pb(y);
	}
	sort(veca.rbegin(), veca.rend());
	sort(vecb.rbegin(), vecb.rend());
	for(int i = 0;i < n;i++)
	{
		a[i + 1] = veca[i];
		b[i + 1] = vecb[i];
		a[i + 1] += a[i];
		b[i + 1] += b[i];
		vals.pb(a[i + 1]);
		vals.pb(b[i + 1]);
	}
	long double ans = 0;
	sort(vals.begin(),vals.end());
	for(auto it : vals)
	{
		int x = lower_bound(a + 1, a + 1 + n, it) - a;
		int y = lower_bound(b + 1, b + 1 + n, it) - b;
		if(x <= n && y <= n) ans = max(ans, it - x - y);
	}
	cout << fixed << setprecision(4) << ans << endl;
	return 0;
}

Compilation message

sure.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 # pragma GCC optimization ("unroll-loops")

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

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

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 5 ms 512 KB Output is correct
14 Correct 4 ms 512 KB Output is correct
15 Correct 3 ms 512 KB Output is correct
16 Correct 3 ms 512 KB Output is correct
17 Correct 149 ms 10672 KB Output is correct
18 Correct 145 ms 10700 KB Output is correct
19 Correct 158 ms 10636 KB Output is correct
20 Correct 149 ms 10704 KB Output is correct
21 Correct 151 ms 10684 KB Output is correct
22 Correct 144 ms 10688 KB Output is correct
23 Correct 140 ms 10744 KB Output is correct
24 Correct 140 ms 10588 KB Output is correct
25 Correct 147 ms 10712 KB Output is correct
26 Correct 148 ms 10684 KB Output is correct