AOJ0614 Railroad Trip

Railroad Trip | Aizu Online Judge

Introduction to Programming Introduction to Algorithms and Data Structures Library of Data Structures Library of Graph Algorithms Library of Computational Geometry Library of Dynamic Programming Library of Number Theory

移動が終わった時に，各鉄道に何回乗ったか知りたい．imosで累積和を求めた後に，各鉄道に対して，切符を買って乗るか，その鉄道のICカードを書いICカードで乗るか，安い方を選んだ．

  • 切符で乗る
  • ICカードを買う + ICカードで乗る

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

ll cnt[100005];
vector<ll> p, a, b, c;

int main() {
  int n, m;
  cin >> n >> m;

  p.resize(m);
  rep(i, m) {
      cin >> p[i];
      p[i]--;
  }

  a.resize(n-1);
  b.resize(n-1);
  c.resize(n-1);

  rep(i, n-1) {
      cin >> a[i] >> b[i] >> c[i];
  }

  rep(i, m-1) {
      if(p[i] == p[i+1]) continue;

      if(p[i] < p[i+1]) {
          cnt[p[i]]++;
          cnt[p[i+1]]--;
      } else {
          cnt[p[i+1]]++;
          cnt[p[i]]--;
      }
  }

  rep(i, 100005) {
      cnt[i+1] += cnt[i];
  }

  ll ans = 0;
  rep(i, n-1) {
      ans += min(cnt[i] * a[i], cnt[i] * b[i] + c[i]);
  }

  cout << ans << endl;

  return 0;
}
Mar 18th, 2016
aoj, imos法