結果
問題 | No.865 24時間降水量 |
ユーザー |
![]() |
提出日時 | 2019-08-16 22:46:04 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 424 ms / 2,000 ms |
コード長 | 1,599 bytes |
コンパイル時間 | 1,645 ms |
コンパイル使用メモリ | 169,340 KB |
実行使用メモリ | 6,528 KB |
最終ジャッジ日時 | 2024-09-22 19:11:46 |
合計ジャッジ時間 | 3,959 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>typedef long long ll;using namespace std;#define DUMP(x) cout << #x << " = " << (x) << endl;#define FOR(i, m, n) for(ll i = m; i < n; i++)#define IFOR(i, m, n) for(ll i = n - 1; i >= m; i-- )#define REP(i, n) FOR(i,0,n)#define IREP(i, n) IFOR(i,0,n)#define FOREACH(x,a) for(auto& (x) : (a) )#define ALL(v) (v).begin(), (v).end()//1-indexedclass BIT {public:vector<ll> bit;ll M;BIT(ll M):bit(vector<ll>(M+1, 0)), M(M) {}//a[1] + a[2] + ... + a[i]を求めるll sum(ll i) {if (i==0) return 0;return bit[i] + sum(i-(i&-i));}//a[i] += xvoid add(ll i, ll x) {if (i > M) return;bit[i] += x;add(i+(i&-i), x);}};int main(){ll n; cin >> n;// BIT b(n);// REP(i,n){// ll a; cin >> a;// b.add(i+1,a);// }// ll q; cin >> q;// REP(i,q){// ll t,v; cin >> t >> v;// b.add(t,v-(b.sum(t)-b.sum(t-1)));// ll ans = 0;// FOR(j,24,n+1){// ans = max(ans, b.sum(j)-b.sum(j-24));// }// cout << ans << endl;//}//b[i] = a[i] + a[i+1] + ... + a[i+23]//i = 1,2,...,n-23vector<ll> b(n-22,0), a(n+1,0);ll sum = 0;REP(i,n){cin >> a[i+1];if(i<24) sum += a[i+1];}b[1] = sum;ll ans = b[1];FOR(i,1,n-23){sum += a[i+24] - a[i];b[i+1] = sum;ans = max(ans,sum);}ll q; cin >> q;REP(i,q){ll t,v; cin >> t >> v;//bを更新REP(j,24) if(t-23+j>=1 && t-23+j<=n-23){b[t-23+j] += v-a[t];ans = max(ans, b[t-23+j]);}//aを更新a[t] = v;cout << ans << endl;}}