# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
273929 | 2020-08-19T07:54:32 Z | AKaan37 | Santa Claus (RMI19_santa) | C++17 | 1000 ms | 4476 KB |
//Bismillahirrahmanirrahim //█▀█─█──█──█▀█─█─█ //█▄█─█──█──█▄█─█▄█ //█─█─█▄─█▄─█─█─█─█ #include <bits/stdc++.h> using namespace std; typedef long long lo; typedef pair< lo,lo > PII; #define fi first #define se second #define mp make_pair #define endl "\n" #define int long long #define pb push_back #define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) #define FOR for(int i=1;i<=n;i++) #define mid ((start+end)/2) #define ort ((l+r)/2) const lo inf = 300000000000; const lo KOK = 100000; const lo LOG = 30; const lo li = 100005; const lo mod = 1000000007; int n,m,b[li],a[li],k,flag,t,c[li],mx,vis[li],dp[li]; int cev; string s; vector<int> v; inline int naivesol(int x){ if(x<mx)return -1; multiset<int> st; for(int i=1;i<=x;i++)vis[i]=0; for(int i=1;i<=x;i++){ if(b[i]==0){ st.insert(c[i]); continue; } else{ auto it=st.lower_bound(c[i]); if(it!=st.end()){st.erase(it);} else vis[i]=1; } } if((int)st.size()==0)return a[x]; lo mn=inf; //~ cout<<"**\n"; //~ if(x==n-1)cout<<st.size()<<endl; for(int i=x;i>=1;i--){ if(b[i]==0)continue; if(vis[i]==0)continue; //~ if(x==n-1)cout<<i<<"**\n"; auto it=st.lower_bound(c[i]); if(it!=st.end()){mn=min(mn,(lo)i);st.erase(it);} //~ cout<<i<<"\n"; } //~ cout<<(int)st.size()<<endl; if(st.size())return -1; if(mn==inf)mn=0; //~ cout<<a[x]<<endl; return a[x]+(a[x]-a[mn]); } main(void){ scanf("%lld",&t); while(t--){ scanf("%lld",&n); FOR scanf("%lld",&a[i]); FOR scanf("%lld",&b[i]); FOR scanf("%lld",&c[i]); mx=0; FOR{ if(b[i]==0)mx=max(mx,i); } //~ dp[n]=naivesol(n); FOR dp[i]=naivesol(i); FOR printf("%lld ",dp[i]); printf("\n"); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 3 ms | 384 KB | Output is correct |
3 | Incorrect | 420 ms | 632 KB | Output isn't correct |
4 | Execution timed out | 1082 ms | 888 KB | Time limit exceeded |
5 | Execution timed out | 1043 ms | 956 KB | Time limit exceeded |
6 | Execution timed out | 1084 ms | 1228 KB | Time limit exceeded |
7 | Execution timed out | 1094 ms | 1912 KB | Time limit exceeded |
8 | Execution timed out | 1052 ms | 2680 KB | Time limit exceeded |
9 | Execution timed out | 1086 ms | 4476 KB | Time limit exceeded |
10 | Execution timed out | 1096 ms | 4472 KB | Time limit exceeded |