Cod sursa(job #1520093)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 8 noiembrie 2015 12:19:55
Problema 1-sir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<fstream>

using namespace std;

ifstream fin( "1-sir.in" ); ofstream fout( "1-sir.out" );

const int nmax = 256;
const int mod = 194767;
const int smax = nmax * (nmax - 1) / 2 + 1;
int d[ 2 ][ 2 * smax + 1 ];

inline int valabs( int x ) {
    if ( x < 0 ) return -x;
    return x;
}
int main() {
    int n, s;
    fin >> n >> s;
    if ( s > (n - 1) * n / 2 || s < -n * (n - 1) / 2 ) {
        fout << "0\n";
    } else {
        int ind = 0;
        d[ 1 ][ 0 ] = 1;
        for( int i = 2; i <= n; ++ i, ind = 1 - ind ) {
            for( int j = 0; j <= (i - 1) * i / 2; ++ j ) {
                d[ ind ][ j ] = d[ 1 - ind ][ valabs( j - (i - 1) ) ];
                d[ ind ][ j ] += d[ 1 - ind ][ j + (i - 1) ];

                if ( d[ ind ][ j ] >= mod ) {
                    d[ ind ][ j ] -= mod;
                }
            }
        }
        if ( s < 0 ) s = -s;
        fout << d[ 1 - ind ][ s ] << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}