Submission #1364276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1364276		mythofys	Dubai Chewy Cookie (KAISTRUN26SPRING_C)	C++20	100 / 100	24 ms	544 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define inf 4000000000000000000
#define mod 998244353
#define siz 524288

vector < ll > both,o,t;
ll p[2005],one[2005],two[2005];
ll dpb[2005],dpo[2005],dpt[2005],r[2005];

int main()
{
    ll i,j,k,n,m,q;
    scanf("%lld %lld %lld",&n,&m,&q);
    for(i=1;i<=n;i++)
    {
        scanf("%lld",&p[i]);
    }
    for(i=1;i<=m;i++)
    {
        ll u,v;
        scanf("%lld %lld",&u,&v);
        if(u == 1)one[v] = 1;
        if(v == 1)one[u] = 1;
        if(u == 2)two[v] = 1;
        if(v == 2)two[u] = 1;
    }
    one[1] = 1;
    two[2] = 1;
    for(i=1;i<=n;i++)
    {
        if(one[i] == 1 && two[i] == 1)both.push_back(i);
        else if(one[i] == 1)o.push_back(i);
        else if(two[i] == 1)t.push_back(i);
    }
    dpb[0] = 1;
    dpo[0] = 1;
    dpt[0] = 1;
    for(i=0;i<both.size();i++)
    {
        for(j=0;j<=n;j++)
        {
            r[j] += dpb[j] * (1 - p[both[i]] + mod) % mod;
            r[j+1] += dpb[j] * p[both[i]] % mod;
            r[j] %= mod;
            r[j+1] %= mod;
        }
        for(j=0;j<=n;j++)
        {
            dpb[j] = r[j];
            r[j] = 0;
        }
    }
    for(i=0;i<o.size();i++)
    {
        for(j=0;j<=n;j++)
        {
            r[j] += dpo[j] * (1 - p[o[i]] + mod) % mod;
            r[j+1] += dpo[j] * p[o[i]] % mod;
            r[j] %= mod;
            r[j+1] %= mod;
        }
        for(j=0;j<=n;j++)
        {
            dpo[j] = r[j];
            r[j] = 0;
        }
    }
    for(i=0;i<t.size();i++)
    {
        for(j=0;j<=n;j++)
        {
            r[j] += dpt[j] * (1 - p[t[i]] + mod) % mod;
            r[j+1] += dpt[j] * p[t[i]] % mod;
            r[j] %= mod;
            r[j+1] %= mod;
        }
        for(j=0;j<=n;j++)
        {
            dpt[j] = r[j];
            r[j] = 0;
        }
    }
    for(i=1;i<=q;i++)
    {
        ll a,b,nans = 0;
        scanf("%lld %lld",&a,&b);
        for(j=0;j<=min(a,b);j++)
        {
            nans += dpb[j] * dpo[a - j] % mod * dpt[b - j] % mod;
            nans %= mod;
        }
        printf("%lld\n",nans);
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf("%lld %lld %lld",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         scanf("%lld",&p[i]);
      |         ~~~~~^~~~~~~~~~~~~~
Main.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         scanf("%lld %lld",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         scanf("%lld %lld",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 40 / 40