Submission #927344

#	Time	Username	Problem	Language	Result	Execution time	Memory
927344		boris_mihov	Two Dishes (JOI19_dishes)	C++17	3 / 100	10042 ms	31336 KiB

dishes

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

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

int n, m;
struct Dish
{
    int time;
    llong limit;
    int reward;
    int idx;
    bool type;
};

Dish a[MAXN];
Dish b[MAXN];
llong prefixA[MAXN];
llong prefixB[MAXN];
bool isNext[MAXN];
bool isActive[MAXN];
llong dpBorderM[MAXN];
llong dp[MAXN];

int globalRow;
llong findValue(int col)
{
    if (isNext[col])
    {
        llong res = findValue(col + 1) + (isActive[col] ? b[col].reward : 0);
        assert(res >= dp[col]);
        return res;
    }

    return dp[col];
}

void fix(int col)
{
    assert(col <= m);
    llong curr = dp[col];
    llong next = findValue(col + 1) + (isActive[col] ? b[col].reward : 0);
    if (curr > next) isNext[col] = false;
    else isNext[col] = true;
}

void applyUpdate(int to, int val)
{
    for (int i = 1 ; i <= to ; ++i)
    {
        dp[i] += val;
    }
}

std::vector <int> activateAt[MAXN];
void solve()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        prefixA[i] = prefixA[i - 1] + a[i].time;
    }

    for (int i = 1 ; i <= m ; ++i)
    {
        prefixB[i] = prefixB[i - 1] + b[i].time;
    }

    for (int aPos = n ; aPos >= 1 ; --aPos)
    {
        dpBorderM[aPos] = dpBorderM[aPos + 1] + (prefixA[aPos - 1] + prefixB[m] + a[aPos].time <= a[aPos].limit ? a[aPos].reward : 0);
    }

    for (int i = 1 ; i <= m ; ++i)
    {
        int l = 0, r = n + 2, mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (prefixA[mid - 1] + prefixB[i] <= b[i].limit) l = mid;
            else r = mid;
        }

        activateAt[l].push_back(i);
        // std::cout << "here: " << i << ' ' << l << '\n';
    }

    globalRow = n + 1;
    std::fill(isNext + 1, isNext + m + 1, true);
    std::sort(activateAt[n + 1].begin(), activateAt[n + 1].end(), std::greater <int> ());
    for (const int &idx : activateAt[globalRow])
    {
        isActive[idx] = true;
        fix(idx);
    }

    for (globalRow = n ; globalRow >= 1 ; --globalRow)
    {
        for (const int &idx : activateAt[globalRow])
        {
            dp[idx] = findValue(idx);
        }
    
        int l = 0, r = m + 1, mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (prefixA[globalRow] + prefixB[mid - 1] <= a[globalRow].limit) l = mid;
            else r = mid;
        }

        if (l > 0)
        {
            dp[l] = findValue(l);
        }

        for (const int &idx : activateAt[globalRow])
        {
            isActive[idx] = true;
        }

        if (l > 0) activateAt[globalRow].push_back(l);
        applyUpdate(l, a[globalRow].reward);
        dp[m + 1] = dpBorderM[globalRow];
        activateAt[globalRow].push_back(m);
        std::sort(activateAt[globalRow].begin(), activateAt[globalRow].end(), std::greater <int> ());
        
        // for (const int &idx : activateAt[globalRow])
        // {
        //     std::cout << "fix: " << idx << '\n';
        //     fix(idx);
        //     if (idx > 1) fix(idx - 1);
        // }

        for (int idx = m ; idx >= 1 ; --idx)
        {
            fix(idx);
        }

        // // std::cout << "dp after: " << globalRow << '\n';
        // for (int i = 1 ; i <= m ; ++i)
        // {
        //     std::cout << findValue(i) << ' ';
        // } 

        // std::cout << '\n';
        // std::cout << "active\n";
        // for (int i = 1 ; i <= m ; ++i)
        // {
        //     std::cout << isActive   [i] << ' ';
        // }

        // std::cout << '\n';
        // std::cout << "next\n";
        // for (int i = 1 ; i <= m ; ++i)
        // {
        //     std::cout << isNext[i] << ' ';
        // }

        // std::cout << '\n';
    }

    globalRow++;
    std::cout << findValue(1) << '\n';
}

void input()
{
    std::cin >> n >> m;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> a[i].time >> a[i].limit >> a[i].reward;
        a[i].idx = i;
        a[i].type = false;
    }

    for (int i = 1 ; i <= m ; ++i)
    {
        std::cin >> b[i].time >> b[i].limit >> b[i].reward;
        b[i].idx = i;
        a[i].type = true;
    }
}

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 / 5
• Subtask 2: 3 / 3
• Subtask 3: 0 / 7
• Subtask 4: 0 / 39
• Subtask 5: 0 / 11
• Subtask 6: 0 / 9
• Subtask 7: 0 / 17
• Subtask 8: 0 / 9