JOI2014 本戦 鉄道旅行(Railroad Trip)

問題

Railroad Trip | Aizu Online Judge

解法

i日目にa->bに旅行するとき、[a,b]に含まれる鉄道を全て利用することになるので、まず全日程でどの鉄道が何回利用されるかをいもす法で管理する。
注目した鉄道iが全日程でn回利用されるとき、min(A[i]*n, C[i] + B[i]*n)をコストとして取っていけばよい。O(max(N,M))

コード

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <queue>
#include <complex>
 
#define INF 100000000
#define INF_INT_MAX 2147483647
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
 
using namespace std;

#define MAX_N 100001
#define MAX_M 100001

int N, M;
int P[MAX_M];
LL A[MAX_N], B[MAX_N], C[MAX_N];

bool Input(){

  cin >> N >> M;
  for(int i = 0; i < M; i++){
    scanf("%d", &P[i]);
    P[i]--;
  }
  for(int i = 0; i < N - 1; i++){
    scanf("%lld %lld %lld", &A[i], &B[i], &C[i]);
  }

  return true;

}

LL sum[MAX_N];

//[l,r]
void FillSum(int l, int r){
  if(l  > r)
    swap(l,r);
  sum[l]++;
  sum[r]--;
}

LL Solve(){

  for(int i = 0; i < M-1; i++){
    FillSum(P[i],P[i+1]);
  }

  LL ret = 0;

  for(int i = 0; i < N; i++){
    sum[i+1] += sum[i];
    ret += min(A[i]*sum[i], C[i]+B[i]*sum[i]);
  }

  return ret;

}

int main(){

  Input();

  cout << Solve() << endl;

  return 0;

}