Cod sursa(job #1182091)

Utilizator tudormaximTudor Maxim tudormaxim Data 4 mai 2014 18:50:07
Problema 1-sir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>

#define mod 194767

using namespace std;

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

int abs (int x)
{
    if ( x < 0) return -x;
    return x;
}

int dp[2][131072],n,s;

int main()
{
    fin>>n>>s;

    if (abs (s) > n*(n+1)/2)
    {
        fout<<0;
        return 0;
    }

    dp[0][65536] = 1;

    int minv = 0, maxv = 0;

    int ok = 0;
    for (int i=1; i<n; ++i,ok=1-ok)
    {
        int *p1 = dp[ok] + 65536;
        int *p2 = dp[1-ok] + 65536;

        for (int j=minv; j <= maxv; ++j)
        {
            p2[j+i] += p1[j];
            if (p2[j+i] >= mod) p2[j+i] -= mod;
            p2[j-i] += p1[j];
            if (p2[j-i] >= mod) p2[j-i] -= mod;

            p1[j] = 0;
        }

        minv -= i;
        maxv += i;
    }

    int *p = dp[ok] + 65536;
    fout<<p[s];
}