QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#336805 | #8276. Code Congestion | ucup-team197# | WA | 0ms | 32348kb | C++20 | 1.5kb | 2024-02-24 21:37:10 | 2024-02-24 21:37:11 |
Judging History
answer
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 200 + 3;
const int T = 3e5 + 3;
const ll MOD = 998244353;
ll n, total, a[N], t[N];
ll prefix[N][T], dp[N][T];
ll compute_sum(int i){
ll sum = 0;
for(int j = 0; j <= total; ++j)
sum += dp[i][j];
sum %= MOD;
return sum;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> total;
for(int i = 1; i <= n; ++i)
cin >> a[i];
for(int i = 1; i <= n; ++i)
cin >> t[i];
ll ans = 0;
for(int j = 0; j <= total; ++j)
dp[n + 1][j] = 0;
dp[n + 1][0] = 1;
for(int i = n; i >= 1; --i){
ll curr = a[i] * compute_sum(i + 1) % MOD;
ans += curr;
for(int j = 0; j <= total; ++j){
dp[i][j] = dp[i + 1][j];
if(j >= t[i]){
dp[i][j] += dp[i + 1][j - t[i]];
dp[i][j] %= MOD;
}
}
}
for(int j = 0; j <= total; ++j)
dp[0][j] = 0;
dp[0][0] = 1;
for(int i = 1; i <= n; ++i){
ll curr = a[i] * compute_sum(i - 1) % MOD;
ans += curr;
for(int j = 0; j <= total; ++j){
dp[i][j] = dp[i - 1][j];
if(j >= t[i]){
dp[i][j] += dp[i - 1][j - t[i]];
dp[i][j] %= MOD;
}
}
}
ans %= MOD;
cout << ans << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 11840kb
input:
3 3 2 3 4 1 2 2
output:
40
result:
ok 1 number(s): "40"
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 32348kb
input:
13 96 56231 258305 150103 164646 232643 37457 239584 192517 167805 215281 159832 98020 141006 54 1 38 1 4 1 4 11 1 4 8 22 1
output:
939811145
result:
wrong answer 1st numbers differ - expected: '745634757', found: '939811145'