ACM: 357 – Let Me Count The Ways

Straightforward DP coin change problem. To find the number of possible ways that make up certain amount of money.

My runtime is 0.012. Maybe the way to further reduce runtime is reducing times of i/o?

CODE

#include <iostream>

enum { MAX = 30000 };

int main(){

    const int coin[] = {1, 5, 10, 25, 50};

    long long w[MAX+1] = {};

    w[0] = 1;

    for(int i=0; i<5; ++i)

        for(int j=coin[i]; j<=MAX; ++j)

            w[j] += w[j-coin[i]];

    int n;

    while( scanf("%d", &n) != EOF )

        if( w[n] == 1 )

            printf("There is only 1 way to produce %d cents change.\n", n);

        else

            printf("There are %lld ways to produce %d cents change.\n", w[n], n);

    return 0;

}