Euler 78

#include <iostream>
#include <vector>
using namespace std;

int p[2][(int)1e6+10];

const int mod=1e6;
const int MAX=1e5;

//p[k][n]= p[k-1][n]+p[k][n-k]

int main()
{
    p[0][0]=p[1][0]=1;
    for(int k=1;k<=MAX;++k)
    {
        if(k%(MAX/100)==0)
            cerr<<"R:"<<k/(MAX/100)<<"%"<<endl;
        for(int i=0;i<k;++i)
            p[k%2][i]=p[(k-1)%2][i];
        for(int n=k;n<=MAX;++n)
        {
            p[k%2][n]=p[(k-1)%2][n]+p[k%2][n-k];
            p[k%2][n]%=mod;
            if(n==k and p[k%2][n]==0)
            {
                cout<<n<<"::"<<p[k%2][n]<<endl;
                return 0;
            }
        }
    }
    return 0;
}