Cod sursa(job #2445765)

Utilizator claudiu.gatinaFMI Claudiu Gatina claudiu.gatina Data 5 august 2019 14:21:26
Problema 1-sir Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <cstdio>

using namespace std;

map<pair<int, int>, int> solutions;

int max(int n)
{
  return (n * (n - 1)) >> 1;
}

int solve(int n, int s)
{
  if (s < 0)
    return solve(n, -s);

  pair<int, int> ns = make_pair(n, s);
  int& sol = solutions[ns];
  if (sol)
    return sol;
  int m = max(n);
  if (m < s)
    return 0;
  if (m == s)
    return 1;

  --n;
  sol = (solve(n, s - n) + solve(n, s + n)) % 194767;
  return sol;
}

int main()
{
  freopen("1-sir.in", "r", stdin);
  freopen("1-sir.out", "w", stdout);

  int n, s;
  cin >> n >> s;
  cout << solve(n, s);
  return 0;
}