AtCoder Beginner Contest 057

Submission #1185545

Source codeソースコード

import std.stdio, std.string, std.conv, std.range, std.array, std.algorithm;
import std.uni, std.math, std.container, std.typecons, std.typetuple;
import core.bitop, std.datetime;

void main(){
    int N, A, B;
    readVars(N, A, B);
    auto v = readln.split.to!(long[]);

    auto h1 = new long[](N/2 + 1);
    auto c1 = new long[](N/2 + 1);
    auto h2 = new long[](N - N/2 + 1);
    auto c2 = new long[](N - N/2 + 1);
    dfs(v, 0, N/2, 0, 0, h1, c1);
    dfs(v, N/2, N, 0, 0, h2, c2);

    long max_v = 0, max_num = 0;
    long cnt = 0;

    foreach(i ; 0 .. h1.length){
        foreach(j ; 0 .. h2.length){
            if (A <= (i + j) && (i + j) <= B) {
                auto tot = h1[i] + h2[j];

                if (max_v == 0){
                    max_v = tot;
                    max_num = i + j;
                    cnt = c1[i] * c2[j];
                    continue;
                }

                if (max_v * (i + j) < tot * max_num){
                    cnt = c1[i] * c2[j];
                    max_v = tot;
                    max_num = i + j;
                } else if (max_v * (i + j) == tot * max_num){
                    cnt += c1[i] * c2[j];
                }
            }
        }
    }

    auto ans = 1. * max_v / max_num;
    writefln("%.10f", ans);
    writeln(cnt);
}

void dfs(long[] v, int idx, int end, int cnt, long tot, long[] h, long[] c){
    if (idx == end) {
        if (h[cnt] < tot) {
            h[cnt] = tot;
            c[cnt] = 1;
        } else if (h[cnt] == tot) {
            c[cnt]++;
        }
        return;
    }

    dfs(v, idx + 1, end, cnt + 1, tot + v[idx], h, c);
    dfs(v, idx + 1, end, cnt, tot, h, c);
}

void readVars(T...)(auto ref T args){
    auto line = readln.split;
    foreach(ref arg ; args){
        arg = line.front.to!(typeof(arg));
        line.popFront;
    }
    if(!line.empty){
        throw new Exception("args num < input num");
    }
}

Submission

Task問題 D - Maximum Average Sets
User nameユーザ名 nanae
Created time投稿日時
Language言語 D (DMD64 v2.070.1)
Status状態 AC
Score得点 400
Source lengthソースコード長 1990 Byte
File nameファイル名
Exec time実行時間 856 ms
Memory usageメモリ使用量 256 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt,sample_03.txt,sample_04.txt
All 400 / 400 sample_01.txt,sample_02.txt,sample_03.txt,sample_04.txt,subtask_1_1.txt,subtask_1_10.txt,subtask_1_11.txt,subtask_1_12.txt,subtask_1_13.txt,subtask_1_14.txt,subtask_1_15.txt,subtask_1_2.txt,subtask_1_3.txt,subtask_1_4.txt,subtask_1_5.txt,subtask_1_6.txt,subtask_1_7.txt,subtask_1_8.txt,subtask_1_9.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
sample_04.txt AC 856 ms 256 KB
subtask_1_1.txt AC 1 ms 256 KB
subtask_1_10.txt AC 819 ms 256 KB
subtask_1_11.txt AC 815 ms 256 KB
subtask_1_12.txt AC 819 ms 256 KB
subtask_1_13.txt AC 819 ms 256 KB
subtask_1_14.txt AC 820 ms 256 KB
subtask_1_15.txt AC 821 ms 256 KB
subtask_1_2.txt AC 1 ms 256 KB
subtask_1_3.txt AC 14 ms 256 KB
subtask_1_4.txt AC 27 ms 256 KB
subtask_1_5.txt AC 819 ms 256 KB
subtask_1_6.txt AC 821 ms 256 KB
subtask_1_7.txt AC 820 ms 256 KB
subtask_1_8.txt AC 818 ms 256 KB
subtask_1_9.txt AC 821 ms 256 KB