can anyone help me with this submission? like what case or condition am i missing here?

array's blog

By array, history, 2 years ago, In English

i am getting WA in test 3, probably missing some case that i did not include in my code, but i am unable to find what case i am missing (i am missing brain ofc but what else).

array
2 years ago
6

Comments (5)

Show archived | Write comment?

The-Winner

2 years ago, hide # |

I think you misunderstood the statement, you don't need the number of ways to make $$$c \equiv k \mod 998244353$$$, you need the number of ways to maximize $$$c$$$. Since the number of ways is big (not the maximum value of $$$c$$$), you want that number $$$\mod 998244353$$$.

→ Reply

array

2 years ago, hide # ^ |

yeah but like even if i do only (number of way to maximize c) % MOD

like here:

const ll MOD = 998244353;
void solve(){
    int n;
    cin>>n;
    ll c =0,temp=0,sum =0,count1=1,count2=1;
    vector<ll>arr(n);
    vector<ll>sum_array(n);
    ll minimum_c = INT32_MAX;
    for(int i=0;i<n;i++){
        cin>>arr[i];
        temp += arr[i]; 
        if(minimum_c > temp){
            minimum_c = temp;
        }
        sum_array[i] = temp;
        if(temp>=0){
            count1 = (count1 * 2) % MOD;
        }
    }
    for(int i=0;i<n;i++){
        if(sum_array[i]==minimum_c && minimum_c != 0){
            count2 = (count2 * 2) % MOD;
        }
    }
    int index;
    for(int i=0;i<n;i++){
        if(sum_array[i]==minimum_c && minimum_c != 0){
            index = i;
        }
    }
    for(int i=index+1;i<n;i++){
        if(sum_array[i]<0){
            count1 = (count1 * 2) % MOD;
        }
    }
    ll res = (count1 * max((ll)1,(count2-1)))%MOD;
    cout<<res<<'\n';
}

the number of ways to maximize c depends on count1 and count2, so i am doing % MOD to them only. and isn't, the number of ways to make c=k is equal to the number of ways to maximize c? like k is the maximum value right?

→ Reply