| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1072207 | vjudge1 | Building 4 (JOI20_building4) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*Template by : Melag & Megu*/
#include <bits/stdc++.h>
using namespace std;
/*Pragma*/
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//#pragma GCC target("sse,sse2,ssse3,sse4,abm,mmx,avx,fma")
/*Global Shortcut*/
#define int long long
#define nl "\n"
//#define endl "\n"
#define fl flush
/*Shortcut*/
#define p(type1,type2) pair<type1,type2>
#define vc(type) vector<type>
#define PQ(type) priority_queue<type>
#define PQ2(type) priority_queue<type, vector<type>, greater<type>>
#define ft first
#define sc second
#define ts(val) to_string(val)
#define ti(val) stoi(val)
/*Contaiiner Shortcut*/
#define mmst(array,value) memset(array,value,sizeof(array))
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define Pb push_back
#define pB pop_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
/*Typedeff Re-define*/
typedef unsigned long long ull;
typedef long double ld;
typedef long long ll;
typedef char ch;
typedef string str;
/*Decimal*/
#define decimal(value) cout << fixed << setprecision(value);
/*Constant*/
const int N = 5e5 + 1e1 + 10;
const ll MOD = 998244353;
const ll mod = 1e9 + 7;
const ll inf = 2e18 + 20;
const ld eps = 1e-9;
/*Traversal Moving*/
//int dx[] = {-1,1,0,0};
//int dy[] = {0,0,-1,1};
//str dz[] = {"U","D","L","R"};
/*-------------------------------------------------------------------------------------------------------*/
int a[N], b[N];
int dp[2*N][N];
str DP[2*N][N];
bool f(int idx, int cnt1, int cnt2, int last, int &n){
if(idx==2*n) return true;
if(dp[idx][cnt1] != -1) return dp[idx][cnt1];
bool p,q,r,s; p=q=r=s=0;
if(cnt1 < n) {
if(a[idx] >= last) {p = f(idx+1, cnt1+1, cnt2, a[idx], n);}
if(b[idx] >= last and cnt2 < n) p = p or f(idx+1, cnt1, cnt2+1, b[idx], n);
}
if(cnt2 < n) {
if(a[idx] >= last and cnt1 < n) q = f(idx+1, cnt1+1, cnt2, a[idx], n);
if(b[idx] >= last) q = q or f(idx+1, cnt1, cnt2+1, b[idx], n);
}
return dp[idx][cnt1] = (int)(p or q);
}
void solve() {
mmst(dp,-1);
int n; cin >> n;
for(int i=0;i<2*n;i++) cin >> a[i];
for(int i=0;i<2*n;i++) cin >> b[i];
//cout << ((f(0,0,0,0,n)) ? "YES" : "NO") << nl;
bool valid = f(0,0,0,0,n);
if(!valid) cout << "-1 \n";
else{
}
return;
}
int32_t main(int32_t argc, char *argv[]) {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
int t=1; //cin >> t;
while(t-- > 0) solve();
return 0;
}