結果
問題 | No.2330 Eat Slime |
ユーザー |
|
提出日時 | 2023-04-13 21:28:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 786 ms / 4,000 ms |
コード長 | 1,154 bytes |
コンパイル時間 | 3,725 ms |
コンパイル使用メモリ | 253,972 KB |
最終ジャッジ日時 | 2025-02-12 05:51:46 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n, m; cin >> n >> m;long long x; cin >> x;vector<int> c(n);for(int i = 0; i < n; i++){cin >> c[i]; c[i]--;}vector<int> a(m), b(m);vector<long long> y(m);for(int i = 0; i < m; i++){cin >> a[i] >> b[i] >> y[i];a[i]--, b[i]--;}vector<long long> res(n + 1);for(long long i = 0; i <= n; i++){res[i] = x * i;}vector<vector<long long>> q(5, vector<long long>(n));for(int i = 0; i < m; i++){q[b[i]][a[i]] += y[i];}for(int i = 0; i < 5; i++){vector<long long> p(n);for(int j = 0; j < n; j++){if(c[j] == i){p[j] += 1;}}reverse(q[i].begin(), q[i].end());vector<long long> r = convolution_ll(p, q[i]);for(int j = n - 1; j < 2 * n - 1; j++){res[j - n + 1] += r[j];}}long long ans = *max_element(res.begin(), res.end());cout << ans << endl;}