洛谷 海底高铁

题号:P3406
把数据类型都开成long long,不然等着丢分??

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
#include<iostream>
#include<algorithm>
using namespace std;
int n, m;
long long track_dif[100005], track[100005];
long long P[100005];
long long A[100005], B[100005], C[100005];
long long cost;
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        cin >> P[i];
    }
    for (int i = 1; i <= n - 1; i++){
        cin >> A[i] >> B[i] >> C[i];
    }
    for (int i = 1; i <= m - 1; i++){
        int l = min(P[i], P[i + 1]), r = max(P[i], P[i + 1]);
        track_dif[l]++;
        track_dif[r]--;
    }
    for (int i = 1; i <= n - 1; i++){
        track[i] = track[i - 1] + track_dif[i];
    }
    for (int i = 1; i <= n - 1; i++){
        cost += min(track[i] * A[i], C[i] + track[i] * B[i]);
    }
    cout << cost;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注