이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "biscuits.h"
#include <algorithm>
#include <queue>
#include <iostream>
using ll = long long;
std::vector<ll> dp;
std::vector<ll> sumdp;
std::vector<ll> ori_v;
ll func(std::vector<ll> s,ll x) {
if(s.size() == 0) return 1;
if(s.size() == 1) return s[0] >= x ? 2 : 1;
if((s.back() == ori_v[s.size() - 1] || s.back() >= x) && s.back() != 0){
return sumdp[s.size() - 1];
}
else {
ll cumsum = 0;
for(int q = 0;q < s.size();q++) {
cumsum += s[q] << q;
}
if(cumsum >= x << (s.size() - 1)) {
std::vector<ll> v(s.begin(),s.end());
ll require = x - v.back();
v.pop_back();
int i = v.size() - 1;
while(require > 0) {
require *= 2;
if(require > v[i]) {
require -= v[i];
v[i] = 0;
}
else {
v[i] -= require;
require = 0;
}
--i;
}
return func(v,x) + sumdp[v.size() - 1];
}
else {
s.pop_back();
return func(s,x);
}
}
}
long long count_tastiness(long long x, std::vector<long long> a) {
dp.clear();
sumdp.clear();
ori_v.clear();
std::vector<ll> v;
ll c = 0;
ll i = 0;
while(true) {
c /= 2;
if(i < a.size()) c += a[i++];
if(c >= x) {
v.push_back(x);
c -= x;
}
else {
v.push_back(c);
c = 0;
}
if(c % 2 == 1) {
v.back()++; c--;
}
if(i == a.size() && c == 0) break;
}
v.push_back(0);
ori_v = v;
dp.push_back(v[0] >= x ? 2 : 1);
sumdp.push_back(dp[0]);
ll cum_sum = v[0];
for(int q = 1;q < v.size();q++) {
ll local = 0;
cum_sum += v[q] << q;
if(cum_sum >= x << q) {
ll require = x - v[q];
std::vector<ll> s(v.begin(),v.begin() + q);
int i = s.size() - 1;
while(require > 0 && i >= 0) {
require *= 2;
if(require > s[i]) {
require -= s[i];
s[i] = 0;
}
else {
s[i] -= require;
require = 0;
}
--i;
}
local += func(s,x);
}
dp.push_back(local);
sumdp.push_back(dp.back() + sumdp.back());
}
return sumdp.back();
}
// ll func(std::vector<ll>& s,ll x) {
// if(s.size() == 0) return 1;
// if(s.size() == 1) return s[0] >= x ? 2 : 1;
// if(s.back() == 0 && s[s.size() - 2] > 0) {
// if(s[s.size() - 2] > x - 1){
// }
// else {
// s.pop_back();
// return
// }
// }
// else if(s.back() > 0) {
// std::vector<ll> v(s.begin(),s.end());
// ll cumsum = 0;
// for(int q = 0;q < v.size();q++) {
// cumsum += v[q] << q;
// }
// if(cumsum >= x << (v.size() - 1)) {
// ll require = x - v.back();
// v.pop_back();
// int i = v.size() - 1;
// while(require > 0) {
// require *= 2;
// if(require > v[i]) {
// require -= v[i];
// v[i] = 0;
// }
// else {
// v[i] -= require;
// require = 0;
// }
// --i;
// }
// return func(v,x) + sumdp[v.size() - 1];
// }
// else {
// s.pop_back();
// return func(s,x);
// }
// }
// else {
// s.pop_back();
// return(func(s,x));
// }
// }
컴파일 시 표준 에러 (stderr) 메시지
biscuits.cpp: In function 'll func(std::vector<long long int>, ll)':
biscuits.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for(int q = 0;q < s.size();q++) {
| ~~^~~~~~~~~~
biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:58:8: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | if(i < a.size()) c += a[i++];
| ~~^~~~~~~~~~
biscuits.cpp:70:8: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | if(i == a.size() && c == 0) break;
| ~~^~~~~~~~~~~
biscuits.cpp:78:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int q = 1;q < v.size();q++) {
| ~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |