Submission #367589

#	Time	Username	Problem	Language	Result	Execution time	Memory
367589		ritul_kr_singh	Sure Bet (CEOI17_sure)	C++17	100 / 100	39 ms	3692 KiB

sure

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << " " <<
#define nl << "\n"

int a[100000], b[100000], bet = 10000;

int f(int i, int j){
    return min(a[i]-(j+1)*bet, b[j]-(i+1)*bet);
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    for(int i=0; i<n; ++i){
        string inp0, inp1; cin >> inp0 >> inp1;
        int i0 = 0, i1 = 0;

        int dot = 0;
        for(int j=0; j<inp0.size(); ++j) if(inp0[j]=='.') dot = j;
        if(!dot){
            inp0 += ".0000";
        }else{
            dot = 4-(inp0.size()-dot-1);
            for(int j=0; j<dot; ++j) inp0 += "0";
        }

        dot = 0;
        for(int j=0; j<inp1.size(); ++j) if(inp1[j]=='.') dot = j;

        if(!dot){
            inp1 += ".0000";
        }else{
            dot = 4-(inp1.size()-dot-1);
            for(int j=0; j<dot; ++j) inp1 += "0";
        }
        for(char j : inp0){
            if(j=='.') continue;
            i0 *= 10LL;
            i0 += (j-'0');
        }
        for(char j : inp1){
            if(j=='.') continue;
            i1 *= 10LL;
            i1 += (j-'0');
        }
        a[i] = i0 - bet;
        b[i] = i1 - bet;
    }
    sort(a, a+n, greater<>());
    sort(b, b+n, greater<>());
    for(int i=1; i<n; ++i){
        a[i] += a[i-1];
        b[i] += b[i-1];
    }
    int ans = 0, sub = 0;

    int i = 0, j = 0;
    while(i < n and j < n){
        while(i+1<n and f(i+1, j) >= f(i, j)) ++i;
        ans = max(ans, f(i, j));
        ++j;
    }
    double out = (double)ans;
    out /= 10000.0;
    cout << fixed << setprecision(4);
    cout << out nl;
}

Compilation message (stderr)

sure.cpp: In function 'int main()':
sure.cpp:22:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for(int j=0; j<inp0.size(); ++j) if(inp0[j]=='.') dot = j;
      |                      ~^~~~~~~~~~~~
sure.cpp:31:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for(int j=0; j<inp1.size(); ++j) if(inp1[j]=='.') dot = j;
      |                      ~^~~~~~~~~~~~
sure.cpp:58:18: warning: unused variable 'sub' [-Wunused-variable]
   58 |     int ans = 0, sub = 0;
      |                  ^~~

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