제출 #158888

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
158888		brcode	Sure Bet (CEOI17_sure)	C++14	100 / 100	234 ms	5240 KiB

sure

#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
const int MAXN = 3e5+5;
double a[MAXN];
double b[MAXN];
double prefa[MAXN];
double prefb[MAXN];
int pntr;
double ans=0.0;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
    }
    sort(a+1,a+n+1,greater<double>());
    sort(b+1,b+n+1,greater<double>());
    
    for(int i=1;i<=n;i++){
        prefa[i] = prefa[i-1]+a[i];
        prefb[i] = prefb[i-1]+b[i];
        
    }
    double prev = 0.0;
    for(int i=1;i<=n;i++){
        //cout<<pntr<<endl;
        prev = min(prefa[i]-pntr-i,prefb[pntr]-pntr-i);
        ans = max(ans,prev);
        
        while(pntr<n && min(prefa[i]-pntr-(double)1-(double)i,prefb[pntr+1]-pntr-(double)1-(double)i)>=(double)prev){
         //   cout<<min(prefa[i]-pntr-1-i,prefb[pntr+1]-pntr-1-i)<<" "<<prev<<endl;
            
            prev = min(prefa[i]-pntr-(double)1.0-(double)i,prefb[pntr+1]-pntr-(double)1.0-(double)i);
            pntr++;
        }
        ans = max(ans,prev);
        
    }
    cout << fixed << showpoint;

    cout<<std::setprecision(4)<<ans<<endl;
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 40 / 40