제출 #1031693

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1031693		sopaconk	새로운 문제 (COCI19_akvizna)	C++17	130 / 130	213 ms	4700 KiB

Main

    #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();
        }
    }

컴파일 시 표준 에러 (stderr) 메시지

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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5
• Subtask 22: 5 / 5
• Subtask 23: 5 / 5
• Subtask 24: 5 / 5
• Subtask 25: 5 / 5
• Subtask 26: 5 / 5