제출 #1341625

#제출 시각아이디문제언어결과실행 시간메모리
1341625developinpopBitaro the Brave 2 (JOI25_ho_t2)C++20
100 / 100
369 ms70876 KiB
/*
_____________________.
|____________________|   $$\                                                            $$\           $$\        $$\               
|____________________|   $$ |                                                           \__|          $$ |       $$ |              
|____________________| $$$$$$\    $$$$$$\  $$$$$$\  $$$$$$$\   $$$$$$$\        $$$$$$\  $$\  $$$$$$\  $$$$$$$\ $$$$$$\    $$$$$$$\ 
|____________________| \_$$  _|  $$  __$$\ \____$$\ $$  __$$\ $$  _____|      $$  __$$\ $$ |$$  __$$\ $$  __$$\\_$$  _|  $$  _____|
|____________________|   $$ |    $$ |  \__|$$$$$$$ |$$ |  $$ |\$$$$$$\        $$ |  \__|$$ |$$ /  $$ |$$ |  $$ | $$ |    \$$$$$$\  
                         $$ |$$\ $$ |     $$  __$$ |$$ |  $$ | \____$$\       $$ |      $$ |$$ |  $$ |$$ |  $$ | $$ |$$\  \____$$\ 
                         \$$$$  |$$ |     \$$$$$$$ |$$ |  $$ |$$$$$$$  |      $$ |      $$ |\$$$$$$$ |$$ |  $$ | \$$$$  |$$$$$$$  |
            へ   ♡        \____/ \__|      \_______|\__|  \__|\_______/       \__|      \__| \____$$ |\__|  \__|  \____/ \_______/ 
         ૮ - ՛)                                                                             $$\   $$ |    
         / ⁻ ៸|                                                                              \$$$$$$  |   are human rights :3
     乀 (ˍ,ل ل                                                                               \______/ 
 
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, 
                         tree_order_statistics_node_update>;
template <typename T>
using ordered_multiset = tree<pair<T, long long>, null_type, 
                      less<pair<T, long long>>, rb_tree_tag, 
                         tree_order_statistics_node_update>;
 
using namespace std;
using namespace __gnu_pbds;
 
#define ll long long
#define ull unsigned long long
#define ld long double
#define inf (ll)2e18+4
#define pb push_back
#define se second
#define fi first
#define endl '\n'
#define mp make_pair
#define pll pair<ll,ll>
#define kth_smallest find_by_order
#define num_of_smaller order_of_key
#define fori(x) for(ll i=0;i<x;i++)
#define forj(y) for(ll j=0;j<y;j++)
#define fork(z) for(ll k=0;k<z;k++)
 
#define DEBUG
 
#ifdef DEBUG
#define show(x) cerr<<#x<<" is "<<x<<endl;
#define show2(x,y) cerr<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<endl;
#define show3(x,y,z) cerr<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<" "<<#z<<" is "<<z<<endl;
#define show4(x,y,z,a) cerr<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<" "<<#z<<" is "<<z<<" "<<#a<<" is "<<a<<endl;
#define show_vec(a) for(auto &i:a)cerr<<i<<" ";cerr<<endl;
#define skillissue cerr<<"your code is running\n";
#define getchar_unlocked _getchar_nolock // comment before submission
#else
#define show(x)
#define show2(x,y)
#define show3(x,y,z)
#define show4(x,y,z,a)
#define show_vec(a)
#define skillissue
#endif
 
/*
 
inline int readint() {
    int x=0; char ch=getchar_unlocked(); bool s=1;
    while(ch<'0'||ch>'9'){if(ch=='-')s=0;ch=getchar_unlocked();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar_unlocked();}
    return s?x:-x;
}
 
*/


struct node{
	ll S,E,M,val,lazy;
	node *l,*r;
	node(ll s,ll e){
		S=s;E=e;val=0;lazy=0;
		M=(S+E)>>1;
		if(S==E)return;
		l=new node(S,M);
		r=new node(M+1,E);
	}
	void prop(){
		if(lazy==0 or S==E)return;
		l->val+=lazy;
		r->val+=lazy;
		l->lazy+=lazy;
		r->lazy+=lazy;
		lazy=0;
	}
	void up(ll x,ll y,ll v){
		if(x>E or y<S)return;
		if(x<=S and E<=y){
			val+=v;
			lazy+=v;
			return;
		}
		prop();
		l->up(x,y,v);
		r->up(x,y,v);
		val=max(l->val,r->val);
	}
	ll qry(ll x,ll y){
		if(x>E or y<S)return -inf;
		if(x<=S and E<=y)return val;
		prop();
		return max(l->qry(x,y),r->qry(x,y));
	}
};
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll n;cin>>n;
	ll a[n];fori(n)cin>>a[i];
	ll b[n];fori(n)cin>>b[i];
	node *root=new node(0,n-1);
	fori(n)root->up(i,i,a[i]);
	fori(n-1){
		root->up(i+1,n-1,-b[i]);
	}
	ll ans=root->qry(0,n-1);
	ll sum=0;
	fori(n)sum+=b[i];
	fori(n-1){
		root->up(i+1,n-1,b[i]);
		root->up(i,i,-sum);
		root->up(0,i,b[i]);
		ans=min(ans,root->qry(0,n-1));
	}
	cout<<max(0LL,ans)<<endl;
}
	
	

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...