Created
September 7, 2017 03:21
-
-
Save algon-320/49cb25015c31534d1c094f399ace12c9 to your computer and use it in GitHub Desktop.
853B - Jury Meeting : http://codeforces.com/problemset/problem/853/B / http://codeforces.com/contest/853/submission/30170941
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
using namespace std; | |
#define int long long | |
using ll=long long; | |
using vi=vector<int>; | |
using pii=pair<int,int>; | |
#define ALL(c) begin(c),end(c) | |
#define RALL(c) rbegin(c),rend(c) | |
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i) | |
#define FORE(x,c) for(auto &x:c) | |
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i) | |
#define REP(i,n) REPF(i,0,n) | |
#define REPR(i,n) for(int i=(int)(n);i>=0;--i) | |
#define SZ(c) ((int)c.size()) | |
#define CONTAIN(c,x) (c.find(x)!=end(c)) | |
#define OUTOFRANGE(y,x,h,w) (y<0||x<0||y>=h||x>=w) | |
#define dump(...) | |
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0}; | |
#define INF (1001001001) | |
#define INFLL (1001001001001001001ll) | |
template<class T> ostream& operator << (ostream &os,const vector<T> &v) { | |
ITR(i,begin(v),end(v)) os<<*i<<(i==end(v)-1?"":" "); return os; } | |
template<class T> istream& operator >> (istream &is,vector<T> &v) { | |
ITR(i,begin(v),end(v)) is>>*i; return is; } | |
template<class T> istream& operator >> (istream &is, pair<T,T> &p) { | |
is>>p.first>>p.second; return is; } | |
template<class T>bool chmax(T &a,const T &b) {if(a<b) {a=b;return 1;} return 0;} | |
template<class T>bool chmin(T &a,const T &b) {if(b<a) {a=b;return 1;} return 0;} | |
//------------------------------------------------------------------------------ | |
struct before_main_function { | |
before_main_function() { | |
#ifdef int | |
#undef INF | |
#define INF INFLL | |
#define stoi stoll | |
#endif | |
cin.tie(0);ios::sync_with_stdio(false); | |
cout<<setprecision(15)<<fixed; | |
#define endl "\n" | |
} | |
} before_main_function; | |
//------------------8<------------------------------------8<-------------------- | |
int n,m,k; | |
int cost1[1000006],cost2[1000006],mn1[100005],mn2[100005]; | |
int solve() { | |
REP(i,100005) mn1[i]=mn2[i]=INF; | |
REP(i,1000006) cost1[i]=cost2[i]=-1; | |
cin>>n>>m>>k; | |
vector<vector<int>> fl(m,vector<int>(4)); | |
cin>>fl; | |
sort(ALL(fl)); | |
// 行き | |
set<int> tmp; | |
int d=0; | |
int idx=0; | |
for(d=0; d<=1000006 && idx<m; d++) { | |
while(idx<m && fl[idx][0]==d) { | |
if(fl[idx][2]!=0) { | |
idx++; | |
continue; | |
} | |
tmp.insert(fl[idx][1]); | |
if(mn1[fl[idx][1]-1]>fl[idx][3]) { | |
if(cost1[d]!=-1) { | |
cost1[d]-=mn1[fl[idx][1]-1]; | |
cost1[d]+=fl[idx][3]; | |
} | |
mn1[fl[idx][1]-1]=fl[idx][3]; | |
} | |
idx++; | |
} | |
if(SZ(tmp)<n) { | |
cost1[d]=-1; | |
} else if(SZ(tmp)==n) { | |
cost1[d]=0; | |
REP(i,n) cost1[d]+=mn1[i]; | |
tmp.insert(INF); | |
cost1[d+1]=cost1[d]; | |
} else { | |
cost1[d+1]=cost1[d]; | |
} | |
} | |
tmp.clear(); | |
// 帰り | |
idx=m-1; | |
for(d=1000006; d>=0 && 0<=idx; d--) { | |
while(0<=idx && fl[idx][0]==d) { | |
if(fl[idx][1]!=0) { | |
idx--; | |
continue; | |
} | |
tmp.insert(fl[idx][2]); | |
if(mn2[fl[idx][2]-1]>fl[idx][3]) { | |
if(cost2[d]!=-1) { | |
cost2[d]-=mn2[fl[idx][2]-1]; | |
cost2[d]+=fl[idx][3]; | |
} | |
mn2[fl[idx][2]-1]=fl[idx][3]; | |
} | |
idx--; | |
} | |
if(SZ(tmp)<n) { | |
cost2[d]=-1; | |
} else if(SZ(tmp)==n) { | |
cost2[d]=0; | |
REP(i,n) cost2[d]+=mn2[i]; | |
tmp.insert(INF); | |
cost2[d-1]=cost2[d]; | |
} else { | |
cost2[d-1]=cost2[d]; | |
} | |
} | |
int ans=INF; | |
REP(i,1000006) { | |
if(cost1[i]!=-1) { | |
if(i+k+1<1000006 && cost2[i+k+1]!=-1) { | |
chmin(ans,cost1[i]+cost2[i+k+1]); | |
} | |
} | |
} | |
if(ans==INF) return -1; | |
return ans; | |
} | |
signed main() { | |
cout<<solve()<<endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment