oj.uz

Submission #1031693

# Submission time Handle Problem Language Result Execution time Memory
1031693 2024-07-23T04:27:43 Z sopaconk Akvizna (COCI19_akvizna) C++17
130 / 130
 213 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;
           // deb(i);
            if(dq.size()>1){
               // deb(dq[0].eval(-i));
             //   deb(dq[1].eval(-i));
            }
            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;
        ld ans;
        slv(n,0);
       // deb(dp[0]);
        //deb(cnt[0]);
        ans=dp[0]+(ld) cnt[0]*0;
      //  deb(ans);
        slv(n,1);
    //    deb(dp[0]);
  //      deb(cnt[0]);
        ans=dp[0]+(ld) cnt[0]*1;
//        deb(ans);
        const ld cot=1e-12;
        while(r-l >cot){
            ld m=(l+r)/2;
            slv(n,m);
         //   deb(m);
       //     deb(dp[0]);
     //       deb(cnt[0]);
            ld ans=dp[0]+(ld) cnt[0]*m;
   //         deb(ans);
            if(cnt[0]>k){
                l=m;
            }
            else{
                if(cnt[0]==k){
                    l=m;
                    break;
                }
                r=m;
            }
        }

         ans=dp[0]+(ld) cnt[0]*l;
        cout<<setprecision(9)<<fixed<<ans<<endl;
    }




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

Compilation message

akvizna.cpp: In function 'void solve()':
akvizna.cpp:83:16: warning: unused variable 'ans' [-Wunused-variable]
   83 |             ld ans=dp[0]+(ld) cnt[0]*m;
      |                ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 456 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 5 ms 580 KB Output is correct
3 Correct 5 ms 344 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 4 ms 456 KB Output is correct
3 Correct 5 ms 344 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 4 ms 572 KB Output is correct
3 Correct 4 ms 348 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 5 ms 344 KB Output is correct
3 Correct 4 ms 456 KB Output is correct

Subtask #9
5.0 / 5.0

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

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 5 ms 592 KB Output is correct
3 Correct 6 ms 348 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 4 ms 596 KB Output is correct
3 Correct 5 ms 348 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 5 ms 348 KB Output is correct

Subtask #13
5.0 / 5.0

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

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 4288 KB Output is correct
2 Correct 201 ms 4444 KB Output is correct
3 Correct 183 ms 4444 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 4436 KB Output is correct
2 Correct 195 ms 4696 KB Output is correct
3 Correct 192 ms 4440 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 4440 KB Output is correct
2 Correct 210 ms 4700 KB Output is correct
3 Correct 195 ms 4696 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 4444 KB Output is correct
2 Correct 205 ms 4700 KB Output is correct
3 Correct 189 ms 4444 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 4444 KB Output is correct
2 Correct 210 ms 4700 KB Output is correct
3 Correct 191 ms 4440 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 4700 KB Output is correct
2 Correct 192 ms 4444 KB Output is correct
3 Correct 202 ms 4444 KB Output is correct

Subtask #20
5.0 / 5.0

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

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 4444 KB Output is correct
2 Correct 203 ms 4696 KB Output is correct
3 Correct 188 ms 4444 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 4700 KB Output is correct
2 Correct 206 ms 4700 KB Output is correct
3 Correct 180 ms 4692 KB Output is correct

Subtask #23
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 4696 KB Output is correct
2 Correct 202 ms 4436 KB Output is correct
3 Correct 194 ms 4696 KB Output is correct

Subtask #24
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 4696 KB Output is correct
2 Correct 199 ms 4692 KB Output is correct
3 Correct 201 ms 4700 KB Output is correct

Subtask #25
5.0 / 5.0

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

Subtask #26
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 4696 KB Output is correct
2 Correct 194 ms 4696 KB Output is correct
3 Correct 203 ms 4692 KB Output is correct