Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define gc c=getchar()
- #define r(x) read(x)
- #define ll long long
- template<typename T>
- inline void read(T&x){
- x=0;T k=1;char gc;
- while(!isdigit(c)){if(c=='-')k=-1;gc;}
- while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
- }
- const ll INF=5e12;
- const int N=1e6+7;
- struct Airline{
- ll date,city,cost;
- };
- inline bool cmp(const Airline &a,const Airline &b){
- return a.date<b.date;
- }
- ll CostA[N];
- ll CostB[N];
- ll MinCost[N];
- vector<Airline>A,B;
- int main(){
- // freopen(".in","r",stdin);
- // freopen(".out","w",stdout);
- int n,m,k;r(n),r(m),r(k);
- int MaxA=0;
- int MaxB=0;
- int MinA=1e6;
- int MinB=1e6;
- for(int i=1;i<=m;++i){
- int d,f,t,c;r(d),r(f),r(t),r(c);
- if(f)A.push_back(Airline{d,f,c}),MaxA=max(MaxA,d),MinA=min(MinA,d);
- else B.push_back(Airline{d,t,c}),MaxB=max(MaxB,d),MinB=min(MinB,d);
- }
- sort(A.begin(),A.end(),cmp);
- sort(B.begin(),B.end(),cmp);
- ll sum=n*INF;
- for(int i=1;i<=n;++i)MinCost[i]=INF;
- for(int i=0;i<MinA;++i)CostA[i]=sum;
- for(int i=MinA,j=0;i<=MaxA;++i){
- while(j<A.size()&&i>=A[j].date){
- sum-=MinCost[A[j].city];
- MinCost[A[j].city]=min(MinCost[A[j].city],A[j].cost);
- sum+=MinCost[A[j].city];
- j++;
- }
- CostA[i]=min(CostA[i-1],sum);
- }
- for(int i=MaxA+1;i<=MaxB;++i)CostA[i]=CostA[i-1];
- sum=n*INF;
- ll ans=2*n*INF;
- for(int i=1;i<=n;++i)MinCost[i]=INF;
- for(int i=MaxB,j=B.size()-1;i>=MinB;--i){
- while(j>=0&&i<=B[j].date){
- sum-=MinCost[B[j].city];
- MinCost[B[j].city]=min(MinCost[B[j].city],B[j].cost);
- sum+=MinCost[B[j].city];
- j--;
- }
- CostB[i]=sum;
- if(i-k-1>0){
- ans=min(ans,CostB[i]+CostA[i-k-1]);
- }
- }
- if(ans>INF)ans=-1;
- printf("%lld\n",ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement