제출 #1369923

#제출 시각아이디문제언어결과실행 시간메모리
1369923chikien2009Two Dishes (JOI19_dishes)C++20
100 / 100
1509 ms182948 KiB
#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n, m, temp;
int p[1000001], q[1000001];
long long res;
long long a[1000001], b[1000001], s[1000001], t[1000001];
vector<pair<long long, int>> g[1000001];
map<int, long long> f;

/*
In case I dont remember the solution of this problem, 
the dp formula look like this:

for i = 0 -> n:
    for j = 0 -> m:
        f[i][j] = max(f[i][j - 1], f[i - 1][j] + cost[i][j])

and the grid is number from left to right, from bottom to top
*/

int main()
{
    setup();

    cin >> n >> m;
    f[m + 1] = 1e18;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i] >> s[i] >> p[i];
        a[i] += a[i - 1];
    }
    for (int i = 1; i <= m; ++i)
    {
        cin >> b[i] >> t[i] >> q[i];
        b[i] += b[i - 1];
    }
    for (int i = 1; i <= n; ++i)
    {
        if (a[i] <= s[i])
        {
            temp = upper_bound(b, b + m + 1, s[i] - a[i]) - b; 
            res += p[i];
            g[i].push_back({-p[i], temp});
        }
    }
    for (int i = 1; i <= m; ++i)
    {
        if (b[i] <= t[i])
        {
            temp = upper_bound(a, a + n + 1, t[i] - b[i]) - a;
            if (temp == n + 1) 
            {
                res += q[i];
                continue;
            }
            g[temp].push_back({q[i], i});
        }
    }
    for (int i = 0; i <= n; ++i)
    {
        sort(g[i].begin(), g[i].end(), greater<pair<long long, int>>());
        for (auto &j : g[i])
        {
            for (auto k = f.lower_bound(j.second); j.first < 0; k = f.erase(k))
            {
                j.first += (*k).second;
                j.second = (*k).first;
            }
            f[j.second] += j.first;
        }
    }
    for (int i = 0; i <= m; ++i)
    {
        res += f[i];
    }
    cout << res;
    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…