Да очень круто: https://forum.tatysite.net/showthread.php?t=13334 .

I got time exceeded error. Can somebody tell what is test case? Or tell me how can I optimize my code? I even found to solutions using dp.

void lemontale(int n,int k,vector<vector<BigInt>> &mem){
    BigInt big_n = BigInt(n);
    BigInt big_k = BigInt(k);
    BigInt dva_big = BigInt(2ull);
    if (mem[n-1][k] == BigInt()){
        if (n<0)
            return ;
        else if (k==0 && n==1){
            mem[n-1][k] = BigInt(1);

            }
        else if (k==0){
            lemontale(n-1,k_start,mem);
            mem[n-1][k] = mem[n-2][k_start];

            }
        else if (n<=k){
            BigInt rez = dva_big^big_n;

            mem[n-1][k] = rez;
            }
        else{

                lemontale(n-1,k_start,mem);
                lemontale(n-1,k-1,mem);
                mem[n-1][k] = mem[n-2][k-1]+mem[n-2][k_start];
            }
    }

}
void lemontale2(int n,int k,BigInt* mem){
    BigInt dva_big = BigInt(2ull);

    if (mem[n-1]==BigInt()){
        if (n<=k)
            mem[n-1] = dva_big^BigInt(n);
        else
            for(int i=0;i<=k;i++){
                if (n-i-1 != 0){
                    lemontale2(n-i-1,k,mem);
                    mem[n-1]+=mem[n-i-2];
                }
                else{
                    mem[n-1]+=1;
                }
            }
    }

}

Edited by author 10.01.2024 16:08

Edited by author 10.01.2024 16:09

Edited by author 10.01.2024 16:09

Edited by author 10.01.2024 16:09

Use high precision. . . Long long only has 10 points. . .

Got AC. Made a mistake in printing long number — need no print leading zeros for non-top parts of number

Your answer to 10000 10000 seems correct, except it misses the very first digit.

I also have the same problem.
My algorithm runs in O(nk) time it will surely get TLE...
how to optimize it?

Just use prefix sums to optimise dp.

Edited by author 02.03.2016 13:39

会不会溢出了？用了高精度了吗？

try test when k = 1

sorry got AC.
i calculated power every time which made it slow
later i just multiplied by 2 each time which gave AC

This problem like a 1009 (k=2)
Solution - dp
try to find f[n] through previous values(f[n-1],f[n-2],..)

It is first test, where result exceeded int:
30 30 - this can be

Read the problem statement carefully:

"if a word "lemon" occurs more than K times successively, the problem will be immediately disqualified from the contest"

Why don't you count case LLL and (what is more strange) case BLL??? They both satisfy problem statement requirement. Right answer for test 3 3 is 8.

I am stupid :) now I have problems with WA#11

Edited by author 29.08.2007 23:09