Poj Solution 3046

http://poj.org/problem?id=3046

#include <stdio.h>
#include <memory.h>


int c[1001];
int ans[1001][10000];

int main() {
    int i, j, k, sum, n, a, t, left, right;
    scanf( "%d%d%d%d", &n, &a, &left, &right );

    if( a > 10000 )
        while( printf( "asdf" ) );

    for( i=0; i<n; i++ )
        c[i] = 0;
    for( i=0; i<a; i++ ) {
        scanf( "%d", &t );
        c[t-1]++;
    }

    memset( ans, 0, sizeof ans );
    ans[0][0] = 1;
    sum = 0;

    for( i=0; i<n; i++ ) {
        for( j=0; j<=right && j<=sum; j++ ) {
            for( k=0; k<=c[i]; k++ ) {
                ans[i+1][j+k] += ans[i][j];
                ans[i+1][j+k] %= 1000000;
            }
            
        }
        sum += c[i];
    }

    sum = 0;
    for( i=left; i<=right; i++ )
        sum += ans[n][i];
    printf( "%dn", sum%1000000 );
    return 0;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *