Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

doubt in 356div1 , problem b

Revision en1, by atlasworld, 2019-01-12 20:55:56

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 ?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English atlasworld 2019-01-12 20:55:56 1163 Initial revision (published)