제출 #1205684

#제출 시각아이디문제언어결과실행 시간메모리
1205684AIF_is_carvingColouring a rectangle (eJOI19_colouring)C++20
30 / 100
64 ms17944 KiB
#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL mod = 998244353; void solve() { LL n, m; cin>>n>>m; vector<LL> a, b; LL sum = 0; for(LL i =1; i<=n+m-1; i++){ LL x; cin>>x; a.push_back(x); sum+= x; } for(LL i =1; i<=n+m-1; i++){ LL x; cin>>x; b.push_back(x); sum+=x; } if(n < m){ swap(n, m); swap(a, b); } if(m == 1){ LL ans = 0; for(int i = 0; i<n+m-1; i++){ ans+= min(a[i], b[n+m-2 - i]); } cout<<ans<<"\n"; return; } LL l = max(n, m); vector<LL> Ax, Bx; for(LL i = 1; i<= n - m; i++) Ax.push_back(0); for(LL i = 0; i<a.size(); i++) Ax.push_back(a[i]); for(LL i = 0; i<b.size(); i++) Bx.push_back(b[i]); for(LL i = 1; i<= n - m; i++) Bx.push_back(0); vector<LL> A, B; for(LL i = 0; i<Ax.size(); i++) if(i%2 == 0) A.push_back(Ax[i]); for(LL i = 0; i<Ax.size(); i++) { if(l%2 == 1){ if(i%2 == 0) B.push_back(Bx[i]); } else if(i%2 == 1) B.push_back(Bx[i]); } if(A.size() < B.size()) swap(A, B); // for(auto x: A) cout<<x<<" "; // cout<<"\n"; // for(auto x: B) cout<<x<<" "; // cout<<"\n"; for(LL i = 0; i<A.size()/2; i++){ A[i]+= A[A.size() - i - 1]; } for(LL i = 0; i<B.size()/2; i++){ B[i]+= B[B.size() - i - 1]; } for(LL i = 1; i<=A.size()/2; i++){ A[i]+= A[i-1]; } for(LL i = 1; i<=B.size()/2; i++){ B[i]+= B[i-1]; } A.insert(A.begin(), 0); B.insert(B.begin(), 0); // for(auto x: A) cout<<x<<" "; // cout<<"\n"; // for(auto x: B) cout<<x<<" "; // cout<<"\n"; LL mex1 = 0; for(LL i = 0; i<=A.size()/2; i++){ mex1 = max<LL>(mex1, A[i] + B[A.size()/2-i]); } //cout<<mex1<<"\n"; //cout<<sum - mex<<"\n"; A.clear(); B.clear(); for(LL i = 0; i<Ax.size(); i++) if(i%2 == 1) A.push_back(Ax[i]); for(LL i = 0; i<Ax.size(); i++) { if(l%2 == 1){ if(i%2 == 1) B.push_back(Bx[i]); } else if(i%2 == 0) B.push_back(Bx[i]); } // for(auto x: A) cout<<x<<" "; // cout<<"\n"; // for(auto x: B) cout<<x<<" "; // cout<<"\n"; for(LL i = 0; i<A.size()/2; i++){ A[i]+= A[A.size() - i - 1]; } for(LL i = 0; i<B.size()/2; i++){ B[i]+= B[B.size() - i - 1]; } for(LL i = 1; i<=A.size()/2; i++){ A[i]+= A[i-1]; } for(LL i = 1; i<=B.size()/2; i++){ B[i]+= B[i-1]; } A.insert(A.begin(), 0); B.insert(B.begin(), 0); // for(auto x: A) cout<<x<<" "; // cout<<"\n"; // for(auto x: B) cout<<x<<" "; // cout<<"\n"; LL mex2 = 0; for(LL i = 0; i<=A.size()/2; i++){ mex2 = max<LL>(mex2, A[i] + B[A.size()/2-i]); } //cout<<mex2<<"\n"; cout<<sum - mex1 - mex2<<"\n"; } signed main(){ ios::sync_with_stdio(false); cin.tie(nullptr); LL T=1; //cin >> T; while (T--) solve(); return 0; }
#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...