Cod sursa(job #2270837)

Utilizator giotoPopescu Ioan gioto Data 27 octombrie 2018 17:18:02
Problema Plus Scor 45
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <bits/stdc++.h>
using namespace std;

int S;
int val[4], nr[4];
long long d[2][300005];
long long s[2][300005];
vector <int> v[3];
inline void build(int k, int ok){
    if(v[k].size() == 0){
        d[ok][0] = 1;
        return ;
    }
    int S = 0;
    for(auto it : v[k]) S += it;

    for(int i = 0; i <= v[k][0] ; ++i){
        d[ok][i] = 1;
        if(i > 0) s[ok][i] = s[ok][i - 1] + d[ok][i];
        else s[ok][i] = 1;
    }
    for(int i = v[k][0] + 1; i <= S ; ++i)
        s[ok][i] = s[ok][i - 1];

    for(int w = 1; w < v[k].size() ; ++w){
        for(int i = 0; i <= S ; ++i){
            int j = i - v[k][w];
            if(j < 0)
            d[ok][i] = s[ok][i];
            else
            d[ok][i] = s[ok][i] - s[ok][j];
        }
        s[ok][0] = d[ok][0];
        for(int j = 1; j <= S ; ++j)
            s[ok][j] = s[ok][j - 1] + d[ok][j];
    }
}
int main()
{
    freopen("plus.in", "r", stdin);
    freopen("plus.out", "w", stdout);

    scanf("%d", &S);
    for(int i = 1; i <= 3 ; ++i)
        scanf("%d%d", &nr[i], &val[i]);

    int nr1 = 0, nr0 = 0;
    long long ad = 1;
    for(int i = 1; i <= 3 ; ++i){
        if(val[i] == 0) ad = ad * 1LL * (nr[i] + 1);
        v[val[i] + 1].push_back(nr[i]);
    }

    if(v[2].size() == 0 && S > 0){printf("0"); return 0;}

    build(2, 0);
    build(0, 1);

    long long Sol = 0;
    for(int i = S; i <= 300000 ; ++i){
        if(d[0][i] == 0 || d[1][i - S] == 0) break ;
        Sol = Sol + 1LL * ad * d[0][i] * d[1][i - S];
    }
    printf("%lld", Sol);

    return 0;
}
//
//10000
//13510 1
//12410 1
//13510 -1