atlasworld's blog

By atlasworld, history, 6 years ago, In English

the problem asks to maximize the number of blocks and volume .

from the editorial it is clear that we should select block of sizes a and a-1 for our

optimal answer .

but in code1 mentioned in the editorial , how does the second recursion came in picture .

here is the code :

Your code here...

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

pair<ll,ll> best;

ll my_pow(ll x) { return x * x * x; }

void rec(ll m, ll steps, ll subtracted) {
	if(m == 0) {
		best = max(best, make_pair(steps, subtracted));
		return;
	}
	ll x = 1;
	while(my_pow(x+1) <= m) ++x;
	rec(m - my_pow(x), steps+1, subtracted + my_pow(x));
	if(x - 1 >= 0) 
		***  rec(my_pow(x)-1-my_pow(x-1), steps+1, subtracted + my_pow(x-1));  /// here **** 
}

int main() {
	ll m;
	scanf("%lld", &m);
	rec(m, 0, 0);
	printf("%lld %lldn", best.first, best.second);
	return 0;
}

while subtracting pow(x-1) shouldn't we subtract it from m ? and how the second recursion will lead us to answer ?

  • Vote: I like it
  • 0
  • Vote: I do not like it