結果

問題 No.2694 The Early Bird Catches The Worm
ユーザー Nyaa UruzuNyaa Uruzu
提出日時 2024-03-22 22:40:27
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 144 ms / 2,000 ms
コード長 9,445 bytes
コンパイル時間 2,091 ms
コンパイル使用メモリ 167,052 KB
実行使用メモリ 8,064 KB
最終ジャッジ日時 2024-09-30 12:05:12
合計ジャッジ時間 9,196 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 72
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<iostream>//
#include<algorithm>//
#include<vector>//
#include<string>//
#include<functional>//
#include<set>//
#include<unordered_set>//
#include<map>//
#include<unordered_map>//
#include<queue>//
#include<deque>//
#include<iomanip>//調
#include<tuple>//pair
#include<cmath>//
#include<cctype>//
#include<fstream>//
#include<random>//
using namespace std;
#define rep(i,n) for (long long i=0;i<n;i++)
#define loop(i,m,n) for(long long i=m;i<=n;i++)
#define range(value,range) for(const auto &value : range)
#define ll long long
#define vl vector<long long>
#define vvl vector<vector<long long>>
#define inf 4000000000000000000LL
#define mod 998244353
//#define mod 1000000007
//√調
bool isSqrt(ll n) {
if (n < 0) return false;
ll sqrtN = static_cast<ll>(sqrt(n));
return sqrtN * sqrtN == n;
}
//
ll power(ll A, ll B) {
ll result = 1;
for (ll i=0;i<B;i++){
result *= A;
}
return result;
}
//
vector<ll> makePrime(ll n){
vector<ll> factors;
while (n % 2 == 0) {
factors.push_back(2);
n /= 2;
}
for (ll i=3; i*i<=n;i+=2) {
while (n%i == 0) {
factors.push_back(i);
n /= i;
}
}
if (n > 2) {
factors.push_back(n);
}
return factors;
}
// nkmod
ll power_mod(ll n, ll k) {
long long result = 1;
while (k > 0){
if ((k&1) ==1)result=(result*n)%mod;
n=n*n%mod;
k >>= 1;
}
return result;
}
// nCr
ll ncr(ll n,ll r) {
if(n<r)return 0;
vvl dp(n+1,vl(r+1));
rep (i,n+1)dp[i][0] = 1;
rep (i,r+1)dp[i][i] = 1;
loop (i,1,n){
loop (j,1,min((ll)i-1,r)) {
//nCr= n-1Cr-1 + n-1Cr
dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
}
}
return dp[n][r];
}
//201
string cnvString(const string &str, int mode) {
string result = str;
if (mode == 0) {
//
for (char &c : result) {
c = tolower(c);
}
} else if (mode == 1) {
//
for (char &c : result) {
c = toupper(c);
}
}
return result;
}
//
string cnvBase(const string &str, ll from_base, ll to_base) {
ll num = 0;
//
string num_str=cnvString(str,1);
// 10
for (char digit : num_str) {
num = num * from_base + (isdigit(digit) ? digit - '0' : digit - 'A' + 10);
}
string result;
//
while (num > 0) {
ll remainder = num % to_base;
result.push_back(remainder < 10 ? remainder + '0' : remainder - 10 + 'A');
num /= to_base;
}
//
reverse(result.begin(), result.end());
return result.empty() ? "0" : result;
}
//ax
ll logax(ll a, ll x){
ll result = 0;
ll power = 1;
while (power < x){
power *= a;
result++;
}
return result;
}
//int
ll bigmd(const string &num, int md) {
ll ans = 0;
ll SIZ = 9; //9
ll base = 1000000000;//SIZ0
rep(i,(num.size()-1)/SIZ+1){
ll chunk = 0;
ll l = i*SIZ;
ll r = min((ll)num.size(),l+SIZ);
if(r!=num.size()){
ans = (ans*base+stoll(num.substr(l,r-l)))%md;
}else{
rep(i,r-l)ans*=10;
ans=(ans+stoll(num.substr(l,r-l)))%md;
}
}
return ans;
}
//2p
vector<string> pad(vector<string> &s,char p){
ll h=s.size();
ll w=s[0].size();
vector<string> res(h+2,string(w+2,p));
rep(i,h)rep(j,w)res[i+1][j+1]=s[i][j];
return res;
}
//ax+by=c cgcd(a,b)0,0
pair<ll,ll> ex_euclid(ll a,ll b,ll c){
if(a<0||b<0||c<0){
pair<ll,ll>ans=ex_euclid(abs(a),abs(b),abs(c));
if(a<0)ans.first*=-1;
if(b<0)ans.second*=-1;
if(c<0)ans.first*=-1,ans.second*=-1;
return ans;
}
if(c!=1){
ll d=gcd(a,b);
if(c%d!=0)return make_pair(0,0);
pair<ll,ll>ans = ex_euclid(a/d,b/d,1);
ans.first*=c/d;
ans.second*=c/d;
return ans;
}
if(a<b){
pair<ll,ll>ans=ex_euclid(b,a,c);
swap(ans.first,ans.second);
return ans;
}
if(a==1&&b==0)return make_pair(1,0);
else if(b==0) return make_pair(0,0);
ll x,y;
tie(x,y)=ex_euclid(b,a%b,c);
pair<ll,ll> ans=make_pair(y,x-(a/b)*y);
return ans;
}
// Union-Find
struct UnionFind {
vector<int> par, siz;
UnionFind(int n) : par(n, -1) , siz(n, 1) { }
//
int root(int x) {
if (par[x] == -1) return x;
else return par[x] = root(par[x]);
}
// x y ()
bool issame(int x, int y) {
return root(x) == root(y);
}
// x y
bool unite(int x, int y) {
x = root(x), y = root(y);
if (x == y) return false;
if (siz[x] < siz[y]) swap(x, y);
par[y] = x;
siz[x] += siz[y];
return true;
}
// x
int size(int x) {
return siz[root(x)];
}
};
//UF
struct PotentialUnionFind {
ll n;
vl par, siz, pot;
PotentialUnionFind(ll N) : par(N,-1) , siz(N,1) , pot(N,0){n=N;}
//
ll root(ll x) {
if (par[x] == -1) return x;
ll tmp = root(par[x]);
pot[x] += pot[par[x]];
par[x] = tmp;
return par[x];
}
// x y ()
bool issame(ll x, ll y) {
return root(x) == root(y);
}
//x y "0"
ll potential(ll x,ll y){
if(root(x) != root(y)) return 0;
else return pot[y]-pot[x];
}
//x w y
bool unite(ll x, ll y, ll w) {
ll rx = root(x),ry = root(y);
if (rx == ry) return false;
w += pot[x]-pot[y];
if (siz[rx] < siz[ry]) swap(rx, ry),w*=-1;
par[ry] = rx;
siz[rx] += siz[ry];
siz[ry] = 0;
pot[ry] = w;
return true;
}
// x
ll size(ll x) {
return siz[root(x)];
}
//UnionFind調O(n log n)
void regulation(){
vvl r(n);
rep(i,n)r[root(i)].push_back(i);
rep(i,n){
if(r[i].size()==0)continue;
ll mn = i;
rep(j,r[i].size())if(pot[mn]>pot[r[i][j]])mn=r[i][j];
siz[mn]=siz[i];
siz[i]=0;
ll tmp = pot[mn];
rep(j,r[i].size()){
pot[r[i][j]]-=tmp;
par[r[i][j]] = mn;
}
par[mn]=-1;
}
}
void debug(){
rep(i,n)cout<<setw(4)<<left<<par[i]<<" ";
cout<<endl;
rep(i,n)cout<<setw(4)<<left<<pot[i]<<" ";
cout<<endl;
}
};
//,
template<typename T>
struct SegTree{
ll size;
ll tall;
vector<T> data;
function<T(T,T)> p;
//aputd
SegTree(vector<T> a,function<T(T,T)> put,T d) : data(power(2,logax(2,a.size())+1)) {
size = data.size()/2;
tall=logax(2,size)+1;
p=put;
ll tmp=size;
data = vector<T>(size*2,d);
while(tmp!=0){
if(tmp==size)rep(i,a.size())data[tmp+i]=a[i];
else rep(i,tmp) data[tmp+i]=p(data[2*(tmp+i)],data[2*(tmp+i)+1]);
tmp/=2;
}
}
//tx
void update(ll t,T x){
t+=size;
while(t!=0){
if(t>=size)data[t]=x;
else data[t]=p(data[2*t],data[2*t+1]);
t/=2;
}
}
//l~r
T get(ll l,ll r){
//lr
l=max(0LL,l);
r=min(r,size-1);
r++;
T ans=data[0];
ll pos=l+size;
ll wid=1;
//
while(l+(wid*2)<=r){
while(l%(wid*2)==0&&l+(wid*2)<=r)pos/=2,wid*=2;
ans=p(ans,data[pos]);
pos++;
l+=wid;
}
//
while(l!=r){
while(l+wid>r)pos*=2,wid/=2;
ans=p(ans,data[pos]);
pos++;
l+=wid;
}
return ans;
}
//
void print(){
rep(i,size)cout<<setw(7)<<left<<i;
cout<<endl;
ll pos=size;
rep(i,tall){
rep(j,size){
if(j%power(2,i)==0)cout<<setw(7)<<left<<data[pos],pos++;
else cout<<" ";
}
pos/=4;
cout<<endl;
}
}
};
//
vl dx={1,0,-1,0};
vl dy={0,1,0,-1};
//
random_device rnd;//
mt19937 mt(rnd());// 32
ifstream fin("./DefaultFile");
ofstream fout("./DefaultOutFile");//
//
int main(){
ll n,h;
cin>>n>>h;
vl a(n);
vl b(n);
rep(i,n)cin>>a[i];
rep(i,n)cin>>b[i];
vl imos(n+1);
imos[0]=0;
rep(i,n)imos[i+1]=imos[i]+b[i];
ll ans=0;
ll cost=0;
ll r=-1;
ll tmp=0;
rep(l,n){
while(1){
if(cost>h||r==n){
break;
}else{
ans=max(ans,tmp);
}
r++;
cost+=(r-l+1)*b[r];
tmp+=a[r];
}
cost-=imos[r+1]-imos[l];
tmp-=a[l];
}
cout<<ans<<endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0