Submission #31672436

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); ++i)

std::vector<std::string> split(const std::string& text, const char delim);

using ll = long long int;
using llu = unsigned long long int;

int main(){
    string buffer;
    getline(cin, buffer);
    auto input_list = split(buffer, ' ');
    const int N = stoi(input_list[0]);
    const int W = stoi(input_list[1]);

    getline(cin, buffer);
    vector<int> a_list;
    a_list.reserve(N+1);
    for(const auto& str_item : split(buffer, ' ')){
        a_list.emplace_back(stoi(str_item));
    }

    map<int, int> number_map;

    // N=1の処理
    for(const auto& a : a_list){
        number_map[a]++;
    }

    if(N <= 1){
        int count = 0;
        for(const auto& pair : number_map){
            if(W < pair.first){
                break;
            }
            ++count;
        }
        cout << count << endl;
        return 0;
    }

    // N=2の処理
    for(int i = 0; i < N-1; ++i){
        for(int j = i + 1; j < N; ++j){
            const int sum = a_list[i] + a_list[j];
            number_map[sum]++;
        }
    }

    if(N <= 2){
        int count = 0;
        for(const auto& pair : number_map){
            if(W < pair.first){
                break;
            }
            ++count;
        }
        cout << count << endl;
        return 0;
    }

    // N=3の処理
    for(int i = 0; i < N - 2; ++i){
        for(int j = i + 1; j < N - 1; ++j){
            for(int k = j + 1; k < N; ++k){
                const int sum = a_list[i] + a_list[j] + a_list[k];
                number_map[sum]++;
            }
        }
    }

    int count = 0;
    for(const auto& pair : number_map){
        if(W < pair.first){
            break;
        }
        ++count;
    }
    cout << count << endl;

    return 0;
}

std::vector<std::string> split(const std::string& text, const char delim){
    std::vector<std::string> item_list;
    std::stringstream ss(text);
    std::string buffer;

    const size_t NUM_ITEM = std::count(text.begin(), text.end(), delim);
    item_list.reserve(NUM_ITEM + 1);

    while ( std::getline(ss, buffer, delim) ) {
        if (!buffer.empty()) {
                item_list.emplace_back(buffer);
        }
    }

    return item_list;
}

Submission Info

Judge Result