oj.uz

Submission #939308

# Submission time Handle Problem Language Result Execution time Memory
939308 2024-03-06T08:53:35 Z boris_mihov Treatment Project (JOI20_treatment) C++17
0 / 100
 3000 ms 5816 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 100000 + 10;
const llong INF = 1e18;

int n, m;
struct Interval
{
    int t, l, r, c;
    friend bool operator < (const Interval &a, const Interval &b)
    {
        return a.r < b.r;
    }
};

Interval a[MAXN];
llong dp[MAXN];

void solve()
{
    std::sort(a + 1, a + 1 + n);
    for (int i = n ; i >= 1 ; --i)
    {
        if (a[i].r == m)
        {
            dp[i] = a[i].c;
        } else
        {
            dp[i] = INF;
        }

        for (int j = i + 1 ; j <= n ; ++j)
        {
            if (a[i].r - a[j].l + 1 >= abs(a[i].t - a[j].t))
            {
                dp[i] = std::min(dp[i], dp[j] + a[i].c);
            }
        }

        // std::cout << "dp: "
    }

    llong ans = INF;
    for (int i = 1 ; i <= n ; ++i)
    {
        if (a[i].l == 1)
        {
            ans = std::min(ans, dp[i]);
        }
    }

    if (ans == INF) std::cout << -1 << '\n';
    else std::cout << ans << '\n';
}

void input()
{
    std::cin >> m >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> a[i].t >> a[i].l >> a[i].r >> a[i].c;
    }   
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3053 ms 5816 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3053 ms 5816 KB Time limit exceeded
2 Halted 0 ms 0 KB -