Cod sursa(job #1772146)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 6 octombrie 2016 15:39:19
Problema 1-sir Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include<fstream>
#define mod 194767
using namespace std;
int n, s, i, j, k, x, y, val;
int a[2][2 * 256 * 256];
ifstream fin("1-sir.in");
ofstream fout("1-sir.out");
int main(){
    fin>> n >> s;
    if(n * (n - 1) / 2 < s || s < -n * (n - 1) / 2){
        fout<<"0\n";
        return 0;
    }
    k = 1;
    x = n * (n - 1) / 2;
    a[0][x] = 1;
    for(i = 2; i <= n; i++){
        val = n - i + 1;
        y = x - (n - i) * (n - i + 1) / 2;
        for(j = -y; j <= y; j++){
            a[k][j + x] = 0;
            if(j - val >= -y){
                a[k][j + x] = a[1 - k][j - val + x];
            }
            if(j + val <= y){
                a[k][j + x] = (a[k][j + x] + a[1 - k][j + x + val]) % mod;
            }
        }
        k = 1 - k;
    }
    fout<< a[1 - k][s + x] <<"\n";
    return 0;
}