제출 #1324628

#제출 시각아이디문제언어결과실행 시간메모리
1324628Valters07Two Dishes (JOI19_dishes)C++20
5 / 100
98 ms16148 KiB
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define ld long double
#define en exit(0);
#define pb push_back
#define fi first
#define se second
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e6 + 5;
const ll INF = 1e18 + 5;
ll A[N], S[N], P[N], B[N], T[N], Q[N];
ll prefA[N], prefB[N];
ll prefP[N], prefQ[N];
int main()
{
    fio
//    ifstream cin("in.in");
    int n, m;
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
        cin >> A[i] >> S[i] >> P[i];
    for(int i = 1;i <= m;i++)
        cin >> B[i] >> T[i] >> Q[i];
    ll deadline = S[1];
    for(int i = 1;i <= n;i++)
        prefA[i] = prefA[i - 1] + A[i],
        prefP[i] = prefP[i - 1] + P[i];
    for(int i = 1;i <= m;i++)
        prefB[i] = prefB[i - 1] + B[i],
        prefQ[i] = prefQ[i - 1] + Q[i];
    A[n + 1] = B[m + 1] = INF;
    int it = m; // we take JOI currys with indices 1, 2, ..., it
    ll ans = -INF;
    for(int i = 0;i <= n;i++) // we take IOI Donburis with indices 1, 2, ..., i
    {
        while(it >= 0 && prefA[i] + prefB[it] > deadline)
            it--;
        if(it >= 0 && prefA[i] + prefB[it] <= deadline)
        {
            // we shouldn't be able to take one more item
            ll cur = prefA[i] + prefB[it];
            if(cur + A[i + 1] > deadline && cur + B[it + 1] > deadline)
                ans = max(ans, prefP[i] + prefQ[it]);
        }
    }
    cout << ans;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...