oj.uz

Submission #350003

# Submission time Handle Problem Language Result Execution time Memory
350003 2021-01-18T20:24:27 Z knightron0 Sure Bet (CEOI17_sure) C++14
100 / 100
 116 ms 5584 KB 
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define clr(a) memset(a, 0, sizeof(a))
#define sz(x) x.size()
#define printvector(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout<<*it<<" "; cout<<endl;
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define DEC(i, x, y) for (int i = x; i >= y; i--)
#define all(v) v.begin(), v.end()
#define min3(a, b, c) min(a, min(b, c))
#define max3(a, b, c) max(a, max(b, c))
#define alla(a, n) a, a + n
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * b)/gcd(a, b)
#define int long long int
#define ull unsigned long long
#define printarray(arr, n) for(int i= 0;i<n;i++) cout<<arr[i]<<' '; cout<<endl;
#define printvecpairs(vec) for(auto it: vec) cout<<it.fr<<' '<<it.sc<<endl;
#define initdp(a) memset(a, -1, sizeof(a));
#define endl '\n'
#define float long double

using namespace std;
const int MOD = 1e9 + 7;
const int INF = 2e15;
const int MAXN = 1e5 + 5;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    vector<long double> a, b;
    for(int i = 0;i<n;i++){
    	long double t1, t2;
    	cin>>t1>>t2;
    	a.pb(t1);
    	b.pb(t2);
    }
    sort(all(a));
    reverse(all(a));
    sort(all(b));
    reverse(all(b));
    int i= 0; 
    int j= 0;
    long double suma = 0;
    long double sumb = 0;
    long double ans = (long double)-INF;
    while(i < n || j < n){
    	if(i == n){
    		sumb += b[j];
    		j++;
    		int taken = i+ j;
    		ans = max(ans, min(suma, sumb)-(long double)taken);
    		continue;
    	}
    	if(j == n){
    		suma += a[i];
    		i++;
    		int taken = i+ j;
    		ans = max(ans, min(suma, sumb)-(long double)taken);
    		continue;
    	}
    	if(sumb > suma){
    		suma += a[i];
    		i++;
    		int taken = i+ j;
    		ans = max(ans, min(suma, sumb)-(long double)taken);
    	} else if(sumb < suma){
    		sumb += b[j];
    		j++;
    		int taken = i+ j;
    		ans = max(ans, min(suma, sumb)-(long double)taken);
    	} else {
    		if(b[j] > a[i]){
    			sumb += b[j];
	    		j++;
	    		int taken = i+ j;
	    		ans = max(ans, min(suma, sumb)-(long double)taken);
    		} else {
    			suma += a[i];
	    		i++;
	    		int taken = i+ j;
	    		ans = max(ans, min(suma, sumb)-(long double)taken);
    		}
    	}
    }    
    ans = max(ans, (long double)0);
    cout<<fixed<<setprecision(4)<<ans<<endl;
    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

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

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 2 ms 364 KB Output is correct
13 Correct 2 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 2 ms 364 KB Output is correct
17 Correct 104 ms 5244 KB Output is correct
18 Correct 106 ms 5072 KB Output is correct
19 Correct 107 ms 5072 KB Output is correct
20 Correct 105 ms 5072 KB Output is correct
21 Correct 116 ms 5584 KB Output is correct
22 Correct 107 ms 5096 KB Output is correct
23 Correct 103 ms 5092 KB Output is correct
24 Correct 105 ms 5072 KB Output is correct
25 Correct 105 ms 5200 KB Output is correct
26 Correct 113 ms 5476 KB Output is correct