Submission #1079140

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079140		azberjibiou	Two Dishes (JOI19_dishes)	C++17	100 / 100	1741 ms	317572 KiB

dishes

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=1005000;
const int mxM=1557;
const int mxK=60;
const ll INF=1e18;
int N, M;
ll A[mxN], B[mxN], S[mxN], P[mxN], T[mxN], Q[mxN];
ll pA[mxN], pB[mxN];
vector <pll> cont[mxN];
ll C;
void input(){
    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];
    }
}
void make_prefix(){
    for(int i=1;i<=N;i++) pA[i]=pA[i-1]+A[i];
    for(int i=1;i<=M;i++) pB[i]=pB[i-1]+B[i];
}
void make_score(){
    for(int i=1;i<=N;i++){
        if(S[i]<pA[i]) continue;
        ll t=S[i]-pA[i];
        if(t>=pB[M]){
            C+=P[i];
            continue;
        }
        int idx=lower_bound(pB, pB+M+1, t+1)-pB-1;
        cont[i].emplace_back(idx, P[i]);
    }
    for(int i=1;i<=M;i++){
        if(T[i]<pB[i]) continue;
        ll x=T[i]-pB[i]+1, y=pB[i]-1;
        if(x>pA[N]){
            C+=Q[i];
            continue;
        }
        int ix=lower_bound(pA, pA+N+1, x)-pA, iy=i-1;
        C+=Q[i];
        cont[ix].emplace_back(iy, -Q[i]);
    }
}
void push_set(multiset <pll> &s, pll now){
    if(now.se>0){
        s.insert(now);
        return;
    }
    ll x=-now.se;
    auto it=s.lower_bound(now);
    while(x>0){
        //printf("x=%lld, it=%lld %lld\n", x, it->fi, it->se);
        if(it->se >=x){
            s.insert(pll(it->fi, it->se - x));
            s.erase(it);
            return;
        }
        else{
            x-= it->se;
            auto nit=it;
            nit++;
            s.erase(it);
            it=nit;
        }
    }
}
void make_dp(){
    multiset <pll> s;
    s.insert(pll(INF, INF));
    for(int i=1;i<=N;i++){
        sort(all(cont[i]), [](pll a, pll b){return a.se<b.se;});
        //printf("i=%d\n", i);
        for(auto [pos, val] : cont[i]){
            //printf("(%lld %lld) ", pos, val);
            C+=val;
            push_set(s, pll(pos, -val));
        }
        //printf("\n");
        //printf("C=%lld\n", C);
        //for(pll x : s) printf("(%lld %lld) ", x.fi, x.se);
        //printf("\n");
    }
    auto it=s.end(); it--;
    s.erase(it);
    for(auto x : s) C+=x.se;
    cout << C << '\n';
}
int main(){
    gibon
    input();
    make_prefix();
    make_score();
    make_dp();
}

Compilation message (stderr)

dishes.cpp: In function 'void make_score()':
dishes.cpp:49:28: warning: unused variable 'y' [-Wunused-variable]
   49 |         ll x=T[i]-pB[i]+1, y=pB[i]-1;
      |                            ^

• Subtask 1: 5 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 39 / 39
• Subtask 5: 11 / 11
• Subtask 6: 9 / 9
• Subtask 7: 17 / 17
• Subtask 8: 9 / 9