Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cstring>
- #include <limits>
- #include <algorithm>
- #include <vector>
- #include <map>
- using namespace std;
- int L,M,D,cost[51];
- vector<int> x,to[2002],color[2002],price[2002];
- bool done[2002][51][3];
- pair<long long, int> memo[2002][51][3];
- pair<long long, int> solve(int pos, int last, int cont){
- if(x[pos] == L) return make_pair(0LL,0);
- pair<long long, int> &ret = memo[pos][last][cont];
- if(!done[pos][last][cont]){
- done[pos][last][cont] = true;
- ret = make_pair(numeric_limits<long long>::max(),numeric_limits<int>::max());
- pair<long long, int> aux;
- for(int i = 1;i <= M;++i){
- aux = solve(pos + 1,i,0);
- aux.first += (long long)(x[pos + 1] - x[pos]) * cost[i];
- aux.second += (i != last? 1 : 0);
- ret = min(ret,aux);
- }
- for(int i = to[pos].size() - 1;i >= 0;--i){
- aux = solve(to[pos][i],color[pos][i],color[pos][i] == last? min(cont + 1,2) : 1);
- aux.first += price[pos][i] - (cont == 2? min(price[pos][i],D) : 0);
- aux.second += (color[pos][i] != last? 1 : 0);
- ret = min(ret,aux);
- }
- }
- return ret;
- }
- int main(){
- int T,N;
- int s[1000],e[1000],c[1000],p[1000];
- map<int,int> id;
- scanf("%d",&T);
- for(int tc = 1;tc <= T;++tc){
- scanf("%d %d %d %d",&L,&N,&M,&D);
- for(int i = 1;i <= M;++i)
- scanf("%d",&cost[i]);
- x.clear();
- x.push_back(0);
- x.push_back(L);
- for(int i = 0;i < N;++i){
- scanf("%d %d %d %d",&s[i],&e[i],&c[i],&p[i]);
- x.push_back(s[i] - 1);
- x.push_back(e[i]);
- }
- sort(x.begin(),x.end());
- int sz = unique(x.begin(),x.end()) - x.begin();
- id.clear();
- for(int i = 0;i < sz;++i){
- id[ x[i] ] = i;
- to[i].clear();
- color[i].clear();
- price[i].clear();
- }
- for(int i = 0;i < N;++i){
- int j = id[ s[i] - 1 ];
- to[j].push_back(id[ e[i] ]);
- color[j].push_back(c[i]);
- price[j].push_back(p[i]);
- }
- memset(done,0,sizeof done);
- pair<long long, int> ans = solve(0,0,0);
- printf("Case %d: %lld %d\n",tc,ans.first,ans.second - 1);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement