제출 #928974

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
928974		SUNWOOOOOOOO	비스킷 담기 (IOI20_biscuits)	C++17	42 / 100	1028 ms	21272 KiB

biscuits

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using pLL = array <LL, 2>;

LL count_tastiness(LL x, vector<LL> A) {
    A.resize(61);
    LL ans = 0;
    vector <pLL> dp, ndp, ndp1, ndp2; // {j, dp[i][j]}
    dp.push_back({A[0], 1});
	for (LL i = 0; i < 60; i++){
        if (dp.size() > 200000) break;
        for (pLL elm : dp){
            LL j = elm[0], val = elm[1];
            if (j >= x) ndp1.push_back({A[i + 1] + (j - x) / 2, val});
            ndp2.push_back({A[i + 1] + j / 2, val});
        }
        dp.clear();
        merge(ndp1.begin(), ndp1.end(), ndp2.begin(), ndp2.end(), back_inserter(ndp));
        for (pLL elm : ndp){
            if (dp.empty() || dp.back()[0] != elm[0]) dp.push_back(elm);
            else dp.back()[1] += elm[1];
        }
        ndp.clear();
        ndp1.clear();
        ndp2.clear();
    }

    for (pLL elm : dp) ans += elm[1];
    return ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 21 / 21
• Subtask 4: 0 / 35
• Subtask 5: 0 / 23