제출 #1181394

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1181394		browntoad	비스킷 담기 (IOI20_biscuits)	C++20	100 / 100	7 ms	1040 KiB

biscuits

#include <bits/stdc++.h>
// #include "grader.cpp"
#include "biscuits.h"
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())

const ll maxn = 1e5+5;
const int bloc = 101;

long long count_tastiness(long long x, std::vector<long long> a) {
	ll mxval = 0;
	REP(i, SZ(a)){
		mxval += (1ll<<i) * a[i];
	}
	mxval /= x;
	//ll cnt = 1;

	ll cur = 0, ptr = 1;
    vector<ll> dp(60), pfa(60);
	for (int j = 0; j < 60;j++){
		if (j < SZ(a)) cur += a[j] * (1ll<<j);
        pfa[j] = min(cur/x, (1ll<<j+1)-1);
		if ((1ll<<j) > mxval) {
            if (j > 0) dp[j] = dp[j-1];
            else dp[j] = 1;
            continue;
        }
		/*ll optr = ptr, v;
		REP(i, optr){
			v = okie[i];
			if (v + (1ll<<j) > mxval) break;
			if ((v + (1ll<<j))*x > cur) break;
			okie[ptr++] = (v|(1ll<<j));
		}
        */
       ll tmp = cur, cpos = j;
       while(cpos >= 0){
            tmp = min(pfa[cpos], tmp);
            if (!(tmp&(1ll<<cpos))) {
                cpos--;
                continue;
            }
            if (cpos > 0) dp[j] += dp[cpos-1];
            else dp[j]++;

            //dp[j]++; // end itself as 1
            tmp -= (1ll<<cpos);
            cpos--;
       }
       dp[j]++;
       //cout<<dp[j]<<endl;
	}
	return dp[59];
		//return 0;
}
// answer(j) = answer(j-1) + (if exist bit, after modification)-> answer(j-1)

/*
1
3 3
5 2 1

1
3 2
2 1 2

1
1 1
2
*/

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