結果
問題 | No.2694 The Early Bird Catches The Worm |
ユーザー |
![]() |
提出日時 | 2024-03-22 21:59:15 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 66 ms / 2,000 ms |
コード長 | 1,311 bytes |
コンパイル時間 | 2,309 ms |
コンパイル使用メモリ | 204,820 KB |
実行使用メモリ | 12,608 KB |
最終ジャッジ日時 | 2024-09-30 11:30:58 |
合計ジャッジ時間 | 7,568 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 72 |
ソースコード
#include <bits/stdc++.h>#define int llusing namespace std;#define rep(i,n) for(int i=0;i<n;i++)#define per(i,n) for(int i=n-1;i>=0;i--)#define rng(i,c,n) for(int i=c;i<n;i++)#define fi first#define se second#define pb push_back#define all(a) a.begin(), a.end()#define sz(a) ((int) a.size())#define vec(...) vector<__VA_ARGS__>#define _4ab8goq ios::sync_with_stdio(0),cin.tie(0);typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pii;void print(){cout<<'\n';}template<class h,class...t>void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}void slv(){int n,h;cin>>n>>h;vi a(n);rep(i,n){cin>>a[i];}vi b(n);rep(i,n){cin>>b[i];}vi ps_a;rep(i,n){ps_a.pb((sz(ps_a)?ps_a.back():0)+a[i]);}vi ps_bc;rep(i,n){ps_bc.pb((sz(ps_bc)?ps_bc.back():0)+i*b[i]);}vi ps_b;rep(i,n){ps_b.pb((sz(ps_b)?ps_b.back():0)+b[i]);}auto range_sum=[&](vi&ps,int l,int r)->int{return ps[r]-(!l?0:ps[l-1]);};int ans=0;rep(i,n){int l=0,r=i;int opt=-1;while(l<=r){int m=(l+r)/2;int now=range_sum(ps_bc,m,i);now-=(m-1)*range_sum(ps_b,m,i);if(now<=h){opt=m,r=m-1;}else{l=m+1;}}if(opt!=-1){ans=max(ans,range_sum(ps_a,opt,i));}}cout<<ans<<"\n";}signed main(){_4ab8goq;slv();}