제출 #485987

#제출 시각아이디문제언어결과실행 시간메모리
485987keertan은행 (IZhO14_bank)C++17
100 / 100
170 ms8520 KiB
/** * If you live in imaginary world when your imaginary situation encounter in * real situation you can't enjoiy it because you have to do pending work. * {This pending work appeared because you wasted that time for your useless * imagianry thinking .} */ #include<bits/stdc++.h> using namespace std; //#define int int64_t #define all(x) x.begin(),x.end() #define all1(x) x.rbegin(),x.rend() const int N=2e5+5; void solve(){ int n,m; cin>>n>>m; int pers[n],cur[m]; for (int i=0;i<n;i++){cin>>pers[i];} for (int i=0;i<m;i++){cin>>cur[i];} int dp[1<<m],remaining[1<<m]; memset(dp,-1,sizeof(dp)); memset(remaining,-1,sizeof(remaining)); dp[0]=remaining[0]=0; for (int msk=1;msk<(1<<m);msk++){ for (int bt=0;bt<m;bt++){ int prv=msk^(1<<bt); if (dp[prv]==-1){continue;} int cura=remaining[prv]+cur[bt]; int req=pers[dp[prv]]; if (cura<req){ dp[msk]=dp[prv]; remaining[msk]=cura; } else if (cura==req){ dp[msk]=dp[prv]+1; remaining[msk]=0; } } if (dp[msk]==n){ cout<<"YES"; return; } } cout<<"NO"; } int32_t main(){ ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); int tq=1; //cin>>tq; for (;tq;tq--){solve();} } //is a bruteforce possible? //think greedier, make more assumptions // if we you find solution using loop to decrease complexity use bs //stuck for more than 5 minutes? move on
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...