oj.uz

Submission #1031684

# Submission time Handle Problem Language Result Execution time Memory
1031684 2024-07-23T04:07:34 Z sopaconk Akvizna (COCI19_akvizna) C++17
65 / 130
 221 ms 4700 KB 
    #include<bits/stdc++.h>
    using namespace std;
    #define pb push_back
    using lli=long long int;
    #define deb(x) cout<<#x<<": "<<x<<endl;
    #define endl '\n'
    using ld=long double;

    
    struct Line{
        ld m;
        ld b;
        lli ind;
        ld eval(ld x) {
            return m*x+b;
        }
        ld intersect (Line l){
            return (ld) (l.b-b)/(m-l.m);
        }

    };

    vector<ld> dp;
    vector<ld> cnt;

    void slv(lli n, ld m){
        deque<Line> dq;
        dp[n]=0;
        cnt[n]=0;
    //    deb(m);
        dq.push_back({1.0/n, 1-m, n});
        for(lli i=n-1; i>=0; --i){
            dp[i]=0;
            cnt[i]=0;
            while(dq.size()>1 && dq[0].eval(-i) < dq[1].eval(-i)){
                dq.pop_front();
            }
            lli id=dq[0].ind;
            dp[i]=dq[0].eval(-i);
            cnt[i]=cnt[id]+1;
       //     deb(i);
         //   deb(dp[i]);
            if(i!=0){
                Line l={1.0/i, 1+dp[i]-m, i};
                while(dq.size()>1 && dq.back().intersect(l)<= dq.back().intersect(dq[dq.size()-2])){
                    dq.pop_back();
                }
                dq.push_back(l);
            }
        }
    }

    void solve(){
        lli n,k;
        cin>>n>>k;
        dp.resize(n+1,0);
        cnt.resize(n+1,0);
        ld l=0;
        ld r=1;
        const ld cot=1e-12;
        while(r-l >cot){
            ld m=(l+r)/2;
            slv(n,m);
     //       deb(dp[0]);
       //     deb(cnt[0]);
     //       ld ans=dp[0]+(ld) cnt[0]*m;
         //   deb(ans);
            if(cnt[0]>=k){
                l=m;
            }
            else{
                r=m;
            }
        }

        ld ans=dp[0]+(ld) cnt[0]*r;
        cout<<setprecision(10)<<ans<<endl;
    }




    int main(){
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        lli t=1;
     //   cin>>t;
        while(t--){
            solve();
        }
    }

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 348 KB Output is correct
2 Incorrect 7 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 348 KB Output is correct
2 Incorrect 6 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 572 KB Output is correct
2 Correct 6 ms 344 KB Output is correct
3 Incorrect 7 ms 576 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 4444 KB Output is correct
2 Correct 202 ms 4444 KB Output is correct
3 Correct 200 ms 4440 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 4440 KB Output is correct
2 Correct 196 ms 4700 KB Output is correct
3 Correct 178 ms 4440 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 4444 KB Output is correct
2 Correct 208 ms 4696 KB Output is correct
3 Correct 202 ms 4700 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 4444 KB Output is correct
2 Correct 200 ms 4700 KB Output is correct
3 Correct 179 ms 4440 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 4444 KB Output is correct
2 Correct 202 ms 4696 KB Output is correct
3 Correct 178 ms 4440 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 4700 KB Output is correct
2 Correct 195 ms 4444 KB Output is correct
3 Correct 181 ms 4444 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 4696 KB Output is correct
2 Correct 187 ms 4440 KB Output is correct
3 Correct 179 ms 4444 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 4444 KB Output is correct
2 Correct 203 ms 4696 KB Output is correct
3 Correct 165 ms 4440 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 4696 KB Output is correct
2 Correct 204 ms 4696 KB Output is correct
3 Correct 189 ms 4696 KB Output is correct

Subtask #23
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 4696 KB Output is correct
2 Correct 192 ms 4444 KB Output is correct
3 Correct 185 ms 4568 KB Output is correct

Subtask #24
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 4700 KB Output is correct
2 Correct 214 ms 4696 KB Output is correct
3 Correct 200 ms 4700 KB Output is correct

Subtask #25
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 4696 KB Output is correct
2 Correct 202 ms 4700 KB Output is correct
3 Correct 207 ms 4700 KB Output is correct

Subtask #26
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 4696 KB Output is correct
2 Correct 207 ms 4700 KB Output is correct
3 Correct 204 ms 4696 KB Output is correct