Cod sursa(job #918241)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 18 martie 2013 18:39:47
Problema 1-sir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <fstream>
 
using namespace std;
 
ifstream cin("1-sir.in");
ofstream cout("1-sir.out");
 
const int mod = 194767, SMAX = 1<<15;
inline void getMod(int &val){ val -= val < mod ? 0 : mod;}
int N, S;
int dp[2][SMAX];
 
 
int solve() {
    if(S > N*(N - 1)/2) return 0;
    dp[0][0] = 1;
    const int SUM = N*(N - 1)/2;
    int line = 0;
    for(int i = 1;i < N;i++,line = 1 - line) {
        for(int j = 0;j <= SUM;j++) {
            dp[1 - line][j] = dp[line][j + i] + dp[line][j - i < 0 ? i - j : j - i];
            getMod(dp[1 - line][j]);
        }
    }
    return dp[line][S];
}
 
int main()
{
    cin>>N>>S;
    if(S < 0) S = -S;
    cout<<solve()<<"\n";
    return 0;
}