Submission #1205766

#TimeUsernameProblemLanguageResultExecution timeMemory
1205766AiperiiiStranded Far From Home (BOI22_island)C++20
0 / 100
3 ms4936 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define all(x) x.begin(),x.end() #define ff first #define ss second #define pb push_back const int N=2e5+5; vector <int> g[N]; int sum[N],a[N],ok[N]; void rec(int l,int r){ if(l==r)return; int mx=0,sum=0,fr=0,ind=0; for(int i=l;i<=r;i++){ sum+=a[i]; if(a[i]>mx){ mx=a[i]; ind=i; fr=sum; } } ok[ind]=1; int sum1=fr-mx; int sum2=sum-fr; if(sum1>=mx && l<=ind-1){ rec(l,ind-1); } if(sum2>=mx && ind+1<=r){ rec(ind+1,r); } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); int n,m; cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; } while(m--){ int u,v; cin>>u>>v; g[u].pb(v); g[v].pb(u); } rec(1,n); for(int i=1;i<=n;i++)cout<<ok[i]; } /* 4 4 2 2 4 3 1 2 1 3 2 3 3 4 4 3 4 2 2 1 1 2 3 2 4 1 10 9 10 9 8 7 4 4 3 2 1 1 1 2 1 3 2 4 3 5 5 7 5 8 7 9 8 10 3 6 1110101000 1 1 1 1 1 2 3 4 5 10 3 2 6 3 */
#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...