Submission #1362252

#TimeUsernameProblemLanguageResultExecution timeMemory
1362252weedywelonBitaro the Brave 2 (JOI25_ho_t2)C++20
100 / 100
61 ms27828 KiB
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <limits.h>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <deque>
#include <map>
#include <chrono>
#include <random>
#include <bitset>
#include <tuple>
#define SZ(x) int(x.size())
#define FR(i,a,b) for(int i=(a);i<(b);++i)
#define FOR(i,n) FR(i,0,n)
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define A first
#define B second
#define mp(a,b) make_pair(a,b)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef unsigned __int128 U128;
typedef __int128 I128;
typedef std::pair<int,int> PII;
typedef std::pair<LL,LL> PLL;
using namespace std;

const LL MAXN=5e5+5;
LL a[MAXN], b[MAXN];
LL pb[MAXN], d[MAXN], pm[MAXN], pm2[MAXN];
LL ans[MAXN];

signed main(){
	FAST;
	LL n; cin>>n;
	FR(i,1,n+1) cin>>a[i];
	FR(i,1,n+1){
		cin>>b[i];
		pb[i]=pb[i-1]+b[i];
	}
	FR(i,1,n+1) d[i]=a[i]-pb[i-1];
	pm[0]=-1e18;
	FR(i,1,n+1) pm[i]=max(pm[i-1],d[i]);
	pm2[n+1]=-1e18;
	for (int i=n; i>=1; i--) pm2[i]=max(pm2[i+1],d[i]);
	
	FR(i,1,n+1){
		LL m1=pm[i-1], m2=pm2[i]+pb[i-1], x=pb[n]-pb[i-1];
		ans[i]=max(m2,m1-x);
		//cout<<i<<": "<<m1-x<<" "<<m2<<" "<<pm2[i]<<"\n";
	}
	
	LL res=1e18;
	FR(i,1,n+1) res=min(res,ans[i]);
	cout<<res;
	return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...