結果
問題 | No.2330 Eat Slime |
ユーザー |
![]() |
提出日時 | 2023-05-28 15:04:04 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 878 ms / 4,000 ms |
コード長 | 837 bytes |
コンパイル時間 | 3,595 ms |
コンパイル使用メモリ | 254,260 KB |
最終ジャッジ日時 | 2025-02-13 12:29:46 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
#include<bits/stdc++.h>#include<atcoder/all>using namespace std;using namespace atcoder;typedef modint998244353 mint;typedef long long ll;int main(){int n, m, x; cin >> n >> m >> x;vector<int> c(n);vector<vector<ll>> lst(5, vector<ll>(n));for (int i=0; i<n; i++){cin >> c[i];c[i]--;lst[c[i]][i] += 1;}vector<vector<ll>> bonus(5, vector<ll>(n));for (int i=0; i<m; i++){int a, b, y; cin >> a >> b >> y;a--; b--;bonus[b][a] += y;}for (int i=0; i<5; i++){reverse(lst[i].begin(), lst[i].end());}ll ans = n * x;vector<ll> qr(n);for (int i=0; i<n; i++){qr[i] = i * x;}for (int j=0; j<5; j++){vector<ll> ar = convolution_ll(lst[j], bonus[j]);for (int i=0; i<n; i++){qr[i] += ar[n-1-i];}}for (int i=0; i<n; i++){ans = max(ans, qr[i]);}cout << ans << endl;}