Submission #1205750

#TimeUsernameProblemLanguageResultExecution timeMemory
1205750buet_aluchashiColouring a rectangle (eJOI19_colouring)C++20
0 / 100
48 ms6544 KiB
#include<bits/stdc++.h> #define ll long long #define pll pair<ll,ll> #define INF 1e15 #define N 500005 using namespace std; struct segtree { vector<pll> arr; segtree(ll n):arr(4*n,make_pair((ll)-INF,0ll)) { ; } pll query(ll pos,ll lt,ll rt,ll a,ll b) { if(b<lt || a>rt || b<a || rt<lt) return make_pair((ll)-INF,0ll); if(a<=lt && rt<=b) return arr[pos]; ll mid=(lt+rt)>>1; ll temp=pos<<1; return max(query(temp,lt,mid,a,b),query(temp|1,mid+1,rt,a,b)); } void update(ll pos,ll lt,ll rt,ll a,ll val) { if(a<lt || a>rt || rt<lt) return; if(lt==rt) { arr[pos]={val,lt}; return; } ll mid=(lt+rt)>>1; ll temp=pos<<1; update(temp,lt,mid,a,val),update(temp|1,mid+1,rt,a,val); arr[pos]=max(arr[temp],arr[temp|1]); } }; // int dp[105][105][105]; void solve() { ll n,m; cin>>n>>m; ll sz=2*max(n,m)-1; vector<ll> a(sz),b(sz); ll temp=m>n?sz-(m+n-1):0; for(ll i=0;i<(m+n-1);i++) cin>>a[temp++]; temp=m<n?sz-(m+n-1):0; for(ll i=0;i<(m+n-1);i++) cin>>b[temp++]; ll sum=0; for(ll i=0;i<sz;i++) sum+=a[i]; ll mx=sum; if(sz==3) { mx=min(a[0]+a[2]+b[0]+b[2],mx); } temp=sum; for(ll i=0;i<max(n,m);i++) { temp=temp-a[i]; if(sz-i-1!=i)temp-=a[sz-1-i]; ll j=max(n,m)-1-i; temp+=b[j]; if(sz-1-j!=j)temp+=b[sz-1-j]; // cout<<temp<<" "; mx=min(mx,temp); } sum=0; swap(a,b); for(ll i=0;i<sz;i++) sum+=a[i]; temp=sum; for(ll i=0;i<max(n,m);i++) { temp=temp-a[i]; if(sz-i-1!=i)temp-=a[sz-1-i]; ll j=max(n,m)-1-i; temp+=b[j]; if(sz-1-j!=j)temp+=b[sz-1-j]; mx=min(mx,temp); } cout<<mx<<"\n"; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; // cin >> t; for(int i = 1; i <= t; ++i){ solve(); } }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...