Cod sursa(job #2680369)

Utilizator PatrickCplusplusPatrick Kristian Ondreovici PatrickCplusplus Data 3 decembrie 2020 12:53:43
Problema 1-sir Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <bits/stdc++.h>

using namespace std;

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

const int mod = 194767;
int n, s;
int main(){
    fin >> n >> s;
    int maxim = n * (n + 1) / 2;
    if (s > maxim || s < -maxim){
        fout << 0;
        return 0;
    }
    vector <int> dp[2];
    dp[0].resize(2 * maxim + 4);
    dp[1].resize(2 * maxim + 4);
    dp[n % 2][s + maxim] = 1;
    int p = n % 2;
    for (int i = n - 1; i >= 1; --i){
        p = 1 - p;
        for (int j = -maxim; j <= maxim; ++j){
            if (j + (n - 1) <= maxim && j - (n - i) >= -maxim)
                dp[p][j + maxim] = (dp[1 - p][j + (n - i) + maxim] + dp[1 - p][j - (n - i) + maxim]);
            else if (j + (n - 1) <= maxim){
                 dp[p][j + maxim] = dp[1 - p][j + (n - i) + maxim];
            }
            else if (j - (n - i) >= -maxim){
                 dp[p][j + maxim] = dp[1 - p][j - (n - i) + maxim];
            }
            if (dp[p][j + maxim] >= mod) dp[p][j + maxim] -= mod;
        }
    }
    fout << dp[1][maxim];
    fin.close();
    fout.close();
    return 0;
}