# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
273918 | 2020-08-19T07:52:18 Z | AKaan37 | Santa Claus (RMI19_santa) | C++17 | 1000 ms | 2424 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 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 = 3000000000; 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]); } int main(void){ scanf("%d",&t); while(t--){ scanf("%d",&n); FOR scanf("%d",&a[i]); FOR scanf("%d",&b[i]); FOR scanf("%d",&c[i]); mx=0; FOR{ if(b[i]==0)mx=max(mx,i); } //~ dp[n]=naivesol(n); FOR dp[i]=naivesol(i); FOR printf("%d ",dp[i]); printf("\n"); } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 5 ms | 384 KB | Output is correct |
3 | Incorrect | 331 ms | 504 KB | Output isn't correct |
4 | Execution timed out | 1097 ms | 632 KB | Time limit exceeded |
5 | Execution timed out | 1064 ms | 504 KB | Time limit exceeded |
6 | Execution timed out | 1042 ms | 1016 KB | Time limit exceeded |
7 | Execution timed out | 1088 ms | 896 KB | Time limit exceeded |
8 | Execution timed out | 1085 ms | 1272 KB | Time limit exceeded |
9 | Execution timed out | 1072 ms | 2168 KB | Time limit exceeded |
10 | Execution timed out | 1092 ms | 2424 KB | Time limit exceeded |