oj.uz

답안 #995172

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
995172 2024-06-08T14:46:13 Z browntoad Two Dishes (JOI19_dishes) C++14
0 / 100
 278 ms 71860 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define FOR(i,a,b) for (int i = (a); i<(b); i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define RREP(i,n) for (int i=(n)-1; i>=0; i--)
#define RREP1(i,n) for (int i=(n); i>=1; i--)
#define f first
#define s second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)(x.size())
#define SQ(x) (x)*(x)
#define pii pair<int, int>
#define pip pair<int, pii>
#define ppi pair<pii, int>
#define pdd pair<double ,double>
#define pcc pair<char, char>
#define endl '\n'
//#define TOAD
#ifdef TOAD
#define bug(x) cerr<<__LINE__<<": "<<#x<<" is "<<x<<endl
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#endif

const double PI=acos(-1);
const ll maxn = 1e6+5;
const ll maxm = 3e3+5;
const ll inf = 1ll<<60;
const ll mod = 998244353;

ll pw(ll a, ll p){
    ll ret = 1;
    while(p > 0){
        if (p&1){
            ret *= a;
            ret %= mod;
        }
        a *= a;
        a %= mod;
        p >>= 1;
    }
    return ret;
}
ll inv(ll a){
    return pw(a, mod-2);
}

int n, m;
vector<pip> v;

vector<pip> ina(maxn), inb(maxn);
bool cmp(pip a, pip b){
    if (a.f == b.f){
        return a.s.f > b.s.f;
    }
    return a.f < b.f;
}
signed main(){
    IOS();
    cin>>n>>m;

    vector<int> pfa(n+1), pfb(m+1);
    REP1(i, n){
        cin>>ina[i].f>>ina[i].s.f>>ina[i].s.s;
        pfa[i] = pfa[i-1] + ina[i].f;
    }
    REP1(i, m){
        cin>>inb[i].f>>inb[i].s.f>>inb[i].s.s;
        pfb[i] = pfb[i-1] + inb[i].f;
    }

    REP1(i, n){
        int dd = upper_bound(ALL(pfb), ina[i].s.f - pfa[i])-pfb.begin()-1;
        if (dd >= 0) v.pb({i, {dd, ina[i].s.s}});
    }
    int jsum = 0;
    REP1(i, m){
        int dd = upper_bound(ALL(pfa), inb[i].s.f - pfb[i])-pfa.begin()-1;
        if (dd >= 0){
            jsum += inb[i].s.s;
            if (dd < n) v.pb({dd+1, {i-1, -inb[i].s.s}});
        }
    }

    sort(ALL(v), cmp);

    map<int, int> mp;
    mp[0] = 0;
    for (auto p:v){
        pii ac = p.s;
        mp[0] += ac.s;
        if (ac.s < 0){
            if (ac.f < m) mp[ac.f+1] += -ac.s;
        }
        else {
            auto it = mp.upper_bound(ac.f);
            int rem = ac.s;
            while (it != mp.end() && (*it).s <= rem){
                rem -= (*it).s;
                it = mp.erase(it);
            }
            if (it != mp.end()){
                assert((*it).s > 0);
                mp[(*it).f] = (*it).s - rem;
            }
        }
    }

    int ans = 0;
    for (auto v:mp) ans += v.s;
    cout<<ans+jsum<<endl;

    // testing
    /*
    vector<int> dp(m+1);
    for(auto p:v){
        REP1(i, m){
            if (i <= p.s.f) dp[i] += p.s.s;
            if (i > 0) dp[i] = max(dp[i], dp[i-1]);
        }
    }
    cout<<dp[m]+jsum<<endl;
    */

}
// funny euler tour :)

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 278 ms 71860 KB Output is correct
2 Correct 187 ms 64956 KB Output is correct
3 Correct 113 ms 57280 KB Output is correct
4 Incorrect 214 ms 63672 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 47192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 47192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 47192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 47192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 47192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 278 ms 71860 KB Output is correct
2 Correct 187 ms 64956 KB Output is correct
3 Correct 113 ms 57280 KB Output is correct
4 Incorrect 214 ms 63672 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 278 ms 71860 KB Output is correct
2 Correct 187 ms 64956 KB Output is correct
3 Correct 113 ms 57280 KB Output is correct
4 Incorrect 214 ms 63672 KB Output isn't correct
5 Halted 0 ms 0 KB -