Submission #72463

#	Time	Username	Problem	Language	Result	Execution time	Memory
72463		유애나 (#118)	Hill Reconstruction (FXCUP3_hill)	C++17	100 / 100	348 ms	5424 KiB

hill

#include <bits/stdc++.h>
using namespace std;

using ld = long double;
using ll = long long;

const int N = 300005, TRIAL = 70;

int n;
ll a[N], b[N], c, mb, ma;

int f(ld x){
    mb = 0; ma = 1;
    int lst = n - 1;
    ll s = 0, cs = 0;
    for(int i = n - 2; i >= 0; i--){
        cs += (a[i] * b[i + 1] - b[i] * a[i + 1]);
        if(ld(b[lst] - b[i]) / (a[lst] - a[i]) <= x){
            cs += (a[lst] * b[i] - b[lst] * a[i]);
            s += abs(cs);
            if(ma * (b[lst] - b[i]) > mb * (a[lst] - a[i])){
                mb = b[lst] - b[i];
                ma = a[lst] - a[i];
            }
            lst = i;
            cs = 0;
        }
        if(s > 2 * c) return 0;
    }
    return !lst;
}

int main(){
    scanf("%d%lld", &n, &c);
    for(int i = 0; i < n; i++) scanf("%lld", a + i);
    for(int i = 0; i < n; i++) scanf("%lld", b + i);
    ld l = 0, r = 1e9;
    for(int i = 0; i < TRIAL; i++){
        ld m = (l + r) / 2;
        if(f(m)) r = m;
        else l = m;
    }
    f(l + 1e-9);
    printf("%lld/%lld\n", mb / gcd(mb, ma), ma / gcd(mb, ma));
}

Compilation message (stderr)

hill.cpp: In function 'int main()':
hill.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%lld", &n, &c);
     ~~~~~^~~~~~~~~~~~~~~~~~
hill.cpp:35:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 0; i < n; i++) scanf("%lld", a + i);
                                ~~~~~^~~~~~~~~~~~~~~
hill.cpp:36:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 0; i < n; i++) scanf("%lld", b + i);
                                ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 32 / 32
• Subtask 2: 68 / 68