Submission #1099508

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099508		_8_8_	Treatment Project (JOI20_treatment)	C++17	0 / 100	3025 ms	5968 KiB

treatment

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

const int  N = 2e5 + 12, MOD = (int)1e9 + 7;

const ll inf = 1e18;
ll res = inf, dp[N];
int n, m;
vector<array<int, 4>> a;

bool cmp(array<int, 4> x, array<int, 4> y) {
    return make_pair(x[1], x[2]) < make_pair(y[1], y[2]);
}
void test() {
    cin >> n >> m;
    a.resize(m);
    for(int i = 0; i < m; i++) {
        cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
    }
    sort(a.begin(), a.end(), cmp);
    for(int i = 0; i < m; i++) {
        dp[i] = inf;
    }
    for(int i = 0; i < m && a[i][1] == 1; i++) {
        dp[i] = 0;
    }
    for(int i = 0; i < m; i++) {
        dp[i] += a[i][3];
        if(a[i][2] == n) {
            res = min(res, dp[i]);
        }
        for(int j = i + 1; j < m; j++) {
            ll inter = a[i][2] - a[j][1] + 1, val = abs(a[i][0] - a[j][0]);
            if(inter >= val) {
                dp[j] = min(dp[j], dp[i]);
            }
        }
    }

    if(res == inf) {
        res = -1;
    }
    cout << res << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
    
    int t = 1; 
    // cin >> t;
    
    while(t--) 
        test();
    
    return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 61