MLE 求助

P1255 数楼梯

_zhuchenzhang_ @ 2018-08-05 17:17:00

#include <bits/stdc++.h>
using namespace std;
template <typename _Tp>
inline _Tp Max(_Tp a,_Tp b)
{
    return a>b?a:b;
}
template <typename _Tp>
inline _Tp Min(_Tp a,_Tp b)
{
    return a<b?a:b;
}
struct BN
{
    #define LEN_SIZE 10001
    private:
        /********************************************************/// user member
        int len;
        int a[LEN_SIZE];
        bool is_nn;//is negative number
    public:
    inline BN UnAbs(BN X)
    {
        X.is_nn=true;
        return X;
    }
    inline BN Abs(BN X)
    {
        X.is_nn=false;
        return X;
    }
    inline void clear() { is_nn=false , memset(a,0,sizeof a) , len=0 ; return; }
    inline void BN_read()
    {
        char t=getchar();
        clear();
        for(;!isdigit(t);t=getchar()) if(t=='-') is_nn=true;
        for(;isdigit(t);t=getchar()) a[++len]=(t-'0');
        return;
    }
    inline void BN_write()
    {
        if(is_nn) putchar('-');
        for(int i=1;i<=len;++i) putchar(a[i]+'0');
        return;
    }
    template <typename _int>
    inline void change(_int A)
    {
        clear();
        if(!A)
        {
            len=1;
            a[1]=0;
            is_nn=false;
            return;
        }
        _int _A=A;
        if(_A<0) _A=-_A,is_nn=true;
        for(;_A;++len,_A/=10);
        _A=A;
        if(is_nn) _A=-_A;
        for(int i=len;i;--i) a[i]=_A%10,_A/=10;
        return;
    }
    BN operator = (const BN &next)
    {
        clear();
        is_nn=next.is_nn;
        len=next.len;
        for(int i=1;i<=next.len;++i) a[i]=next.a[i];
        return *this;
    }
    BN operator + (const BN &next)
    {
        if(!next) return *this;
        if(!(*this)) return next;
        BN temp;
        temp.clear();
        if((next.is_nn&&is_nn)||(!next.is_nn&&!is_nn))
        {
            if(is_nn) temp.is_nn=true;
            BN A,B;
            A.clear(),B.clear();
            A.len=len,B.len=next.len;
            int Len=Max(len,next.len),_len=Min(len,next.len),LEN;
            for(int i=1,I=A.len;i<=A.len&&I;++i,--I) A.a[I]=a[i];
            for(int i=1,I=B.len;i<=B.len&&I;++i,--I) B.a[I]=next.a[i];
            for(int i=1;i<=_len;++i)
            {
                A.a[i]+=B.a[i];
                if(A.a[i]>=10) A.a[i]-=10,A.a[i+1]++;
            }
            for(int i=_len+1;i<=Len;++i)
            {
                if(A.len<B.len) A.a[i]+=B.a[i];
                if(A.a[i]>=10) A.a[i]-=10,A.a[i+1]++;
            }
            for(LEN=LEN_SIZE;!A.a[LEN];--LEN);
            temp.len=LEN;
            for(int i=LEN,I=1;I<=LEN&&i;++I,--i) temp.a[i]=A.a[I];
            return temp;
        }
        else;
    }
    #undef LEN_SIZE
};
int main()
{
    BN A[5001];
    int n;
    scanf("%d",&n);
    A[0].change(0),A[1].change(1),A[2].change(2);
    for(int i=3;i<=n;++i) A[i]=A[i-1]+A[i-2];
    A[n].BN_write();
    return 0;
}

求助大佬,没超时又爆内存


by Marser @ 2018-08-05 17:18:15

BN定义成全局变量


by _zhuchenzhang_ @ 2018-08-05 17:18:33

精简了一部分代码,放不下了。提交记录


by Marser @ 2018-08-05 17:18:56

5000*10000还想不爆内存?


by _zhuchenzhang_ @ 2018-08-05 17:18:59

@Marser 我试试


by _zhuchenzhang_ @ 2018-08-05 17:20:48

@Marser 貌似再一次MLE 记录


by _zhuchenzhang_ @ 2018-08-05 17:21:38

@Marser 好吧没算内存。。。(傻到忘记算内存)


by _zhuchenzhang_ @ 2018-08-05 17:24:04

@Marser 谢谢,过了


by Marser @ 2018-08-05 17:24:34

@zhuchenzhang 不用谢


by 不到前10不改名 @ 2018-08-05 17:45:36

@Marser 我记得100000000都没mle啊!


|