結果

問題 No.576 E869120 and Rings
ユーザー はまやんはまやん
提出日時 2017-10-13 23:04:35
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,996 bytes
コンパイル時間 1,712 ms
コンパイル使用メモリ 172,056 KB
実行使用メモリ 817,920 KB
最終ジャッジ日時 2024-11-17 11:44:25
合計ジャッジ時間 15,627 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22 WA * 2 MLE * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
#define def make_pair(-1, -1)
template<class V, int NV> struct SegTree { //[l,r]
    V comp(V l, V r) { return max(l,r); };
    vector<V> val; SegTree() { val = vector<V>(NV * 2, def); }
    V get(int l, int r) { if (l>r)return def;l+=NV;r+=NV+1;V ret=def; while(l<r){
        if(l&1)ret=comp(ret,val[l++]);if(r&1)ret=comp(ret,val[--r]);l/=2;r/= 2;}return ret;}
    void update(int i, V v) { i+=NV;val[i]=v;while(i>1)i>>=1,val[i]=comp(val[i*2],val[i*2+1]); }
    void add(int i, V v) { update(i, val[i + NV] + v); }};
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/




int N, K; string A;
SegTree<pair<double, int>,1<<20> st;
//---------------------------------------------------------------------------------------------------
int sm[1010101];
double f(int L, int R) {
    int md = (L + R) / 2;

    if (R - L < K) return 0;

    double res = 0;

    res = max(res, f(L, md));
    res = max(res, f(md, R));

    int up = 0, dn = 0;
    rep(i, md, R) {
        if (A[i] == '1') up++, dn++;
        else dn++;
        sm[i] = up;
        st.update(i, make_pair(1.0 * up / dn, i));
    }

    up = 0; dn = 0;
    rrep(i, md - 1, L) {
        if (A[i] == '1') up++, dn++;
        else dn++;

        int j = i + K - 1;
        auto p = st.get(max(j, md), min(R - 1, i + N - 1));
        if (p.second < 0) continue;

        int upp = up + sm[p.second];
        int dnn = p.second - i + 1;

        double e = 1.0 * upp / dnn;
        res = max(res, e);
        assert(e <= 1);

    }

    return res;
}
//---------------------------------------------------------------------------------------------------
double naive() {
    double ans = 0;
    rep(L, 0, N) rep(len, K, N + 1) {
        int R = L + len;

        double up = 0, dn = 0;
        rep(i, L, R) {
            if (A[i] == '0') dn++;
            else up++, dn++;
        }

        ans = max(up / dn, ans);
    }
    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K >> A;
    A += A;
    
    //printf("%.10f\n", naive());
    printf("%.10f\n", f(0, N * 2));
}
0