結果

問題 No.576 E869120 and Rings
ユーザー はまやんはまやんはまやんはまやん
提出日時 2017-10-13 23:04:35
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 401 ms
41,012 KB
testcase_01 AC 413 ms
41,012 KB
testcase_02 AC 410 ms
40,888 KB
testcase_03 WA -
testcase_04 AC 336 ms
40,624 KB
testcase_05 AC 403 ms
40,888 KB
testcase_06 AC 408 ms
40,888 KB
testcase_07 WA -
testcase_08 AC 403 ms
40,976 KB
testcase_09 AC 409 ms
40,984 KB
testcase_10 AC 404 ms
40,980 KB
testcase_11 AC 398 ms
40,892 KB
testcase_12 AC 331 ms
40,504 KB
testcase_13 AC 313 ms
40,628 KB
testcase_14 AC 330 ms
40,756 KB
testcase_15 AC 333 ms
40,664 KB
testcase_16 AC 331 ms
40,608 KB
testcase_17 AC 323 ms
40,632 KB
testcase_18 AC 413 ms
41,008 KB
testcase_19 AC 408 ms
40,972 KB
testcase_20 AC 411 ms
40,888 KB
testcase_21 AC 412 ms
40,848 KB
testcase_22 AC 13 ms
36,096 KB
testcase_23 AC 13 ms
36,096 KB
testcase_24 MLE -
testcase_25 MLE -
testcase_26 MLE -
testcase_27 AC 23 ms
36,276 KB
testcase_28 AC 23 ms
36,224 KB
testcase_29 AC 26 ms
36,224 KB
権限があれば一括ダウンロードができます

ソースコード

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