Submission #17738818

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
void init(int N, vector<vector<int>> &dp, int T, const vector<int> &A_vec,
        const vector<int> &B_vec)
{
    for (int i = 0; i < N; ++i) {
        if (A_vec.at(i) <= T && T <= B_vec.at(i))
            dp.at(0).at(i) = 0;
    }
}
int main()
{
    int D, N;
    cin >> D >> N;
    vector<int> T_vec(D);
    for (int i = 0; i < D; ++i)
        cin >> T_vec.at(i);
    vector<int> A_vec(N), B_vec(N), C_vec(N);
    for (int i = 0; i < N; ++i)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;

void init(int N, vector<vector<int>> &dp, int T, const vector<int> &A_vec,
        const vector<int> &B_vec)
{
    for (int i = 0; i < N; ++i) {
        if (A_vec.at(i) <= T && T <= B_vec.at(i))
            dp.at(0).at(i) = 0;
    }
}

int main()
{
    int D, N;
    cin >> D >> N;
    vector<int> T_vec(D);
    for (int i = 0; i < D; ++i)
        cin >> T_vec.at(i);
    vector<int> A_vec(N), B_vec(N), C_vec(N);
    for (int i = 0; i < N; ++i)
        cin >> A_vec.at(i) >> B_vec.at(i) >> C_vec.at(i);
    vector<vector<int>> dp(D, vector<int>(N, -1));
    init(N, dp, T_vec.at(0), A_vec, B_vec);
    for (int i = 0; i < D - 1; ++i) {
        int T = T_vec.at(i + 1);
        for (int j = 0; j < N; ++j) {
            if (T < A_vec.at(j) || B_vec.at(j) < T)
                continue;
            for (int k = 0; k < N; ++k) {
                int dp_ik = dp.at(i).at(k);
                if (dp_ik == -1)
                    continue;
                int tmp = dp_ik + abs(C_vec.at(k) - C_vec.at(j));
                if (dp.at(i + 1).at(j) < tmp)
                    dp.at(i + 1).at(j) = tmp;
            }
        }
    }
    cout << *max_element(dp.at(D - 1).begin(), dp.at(D - 1).end()) << endl;
}

Submission Info

Judge Result