oj.uz

Submission #491066

# Submission time Handle Problem Language Result Execution time Memory
491066 2021-11-30T09:15:16 Z balbit Two Dishes (JOI19_dishes) C++14
100 / 100
 2540 ms 259600 KB 
#include <bits/stdc++.h>
#undef BALBIT
using namespace std;
#define ll long long
#define int ll
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = LLONG_MAX;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 1e6+5;

int t1[maxn],t2[maxn],d1[maxn],d2[maxn],v1[maxn],v2[maxn]; // time, deadlline, value
ll ps1[maxn], ps2[maxn]; // how much time it takes to get here (before me)

vector<pii> event[maxn]; //

ll df[maxn]; // max a[i] - a[i-1]

//int tmp[500][500];

signed main(){
    IOS();
    int n,m; cin>>n>>m;

    REP(i,n) {
        cin>>t1[i]>>d1[i]>>v1[i];
        ps1[i+1] = ps1[i] + t1[i];
    }

    REP(i,m) {
        cin>>t2[i]>>d2[i]>>v2[i];
        ps2[i+1] = ps2[i] + t2[i];
    }

    ps2[m+1] = ps1[n+1] = inf; // check if inf is big enough later

    ll base = 0; // base value to add to return, used when reversing a range

    REP(i,n) {
        // where can I accept up to???
        ll left = d1[i] - ps1[i+1]; // remaining time after completing this dish
        int pos = upper_bound(ps2, ps2+m+2, left) - ps2 - 1;
        bug(i,pos);
        // when I get to i
        if (pos >= 0) {
            event[i+1].pb({pos, v1[i]});
        }
    }

    bug("moving on");

    REP(i,m) {
        // where can I accept up to???
        ll left = d2[i] - ps2[i+1]; // remaining time after completing this dish
        int pos = upper_bound(ps1, ps1+n+2, left) - ps1 - 1;
        bug(i,pos);
        // when I get to i
        if (pos >= 0 && i >= 0){
            base += v2[i];

            event[pos+1].pb({i, -v2[i]});
            bug(pos, -v2[i]);
        }
    }

    bug(base);

    map<int, ll> mp;

//    mp[m+2] = inf;

    REP(i, n+1) {
        sort(ALL(event[i]), [&](pii a, pii b){ return a.f==b.f?a.s < b.s: a.f > b.f;});
//        ll now = 0;
//        for (pii &p : event[i]) now += p.s;
//        int from = 0;
//        bug(now);
        for (pii &p : event[i]) {
            base += p.s;
            mp[p.f+1] -= p.s;
            if (mp[p.f+1] <= 0) {
                ll poo = mp[p.f+1];
                auto it = mp.erase(mp.find(p.f+1));
                while (poo && it != mp.end()) {
//                    bug(poo, it->f, it->s);
                    it->s += poo;
                    if (it->s <= 0) {
                        poo = it->s;
                        it = mp.erase(it);
                    }else{
                        poo = 0;
                    }
                }
            }
        }
//        for (pii p : event[i]) {
//            REP(j, p.f+1) tmp[i][j] += p.s;
//        }
//        REP(j, 100) {
//            if (i) tmp[i][j] += tmp[i-1][j];
//            if (j) MX(tmp[i][j], tmp[i][j-1]);
//        }

//        REP(j, m+1) {
//            cout<<df[j]<<" \n"[j==m];
//        }
    }

//    cout<<endl<<endl;
//
//    REP(i,n+1) {
//        REP(j, m+1) {
//            cout<<tmp[i][j]<<" \n"[j==m];
//        }
//    }

    for (pii p : mp) {
        bug(p.f, p.s);
        if (p.f <= m)
            base += p.s;
    }

    cout<<base<<endl;


}


/*
1 1
3 10 -3
7 10 5

*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 57412 KB Output is correct
2 Correct 225 ms 46928 KB Output is correct
3 Correct 198 ms 60216 KB Output is correct
4 Correct 253 ms 63348 KB Output is correct
5 Correct 12 ms 23776 KB Output is correct
6 Correct 224 ms 59512 KB Output is correct
7 Correct 86 ms 41148 KB Output is correct
8 Correct 108 ms 43332 KB Output is correct
9 Correct 190 ms 61256 KB Output is correct
10 Correct 182 ms 53276 KB Output is correct
11 Correct 140 ms 54592 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23772 KB Output is correct
2 Correct 12 ms 23816 KB Output is correct
3 Correct 13 ms 23824 KB Output is correct
4 Correct 13 ms 23756 KB Output is correct
5 Correct 12 ms 23812 KB Output is correct
6 Correct 12 ms 23780 KB Output is correct
7 Correct 13 ms 23756 KB Output is correct
8 Correct 14 ms 23756 KB Output is correct
9 Correct 14 ms 23756 KB Output is correct
10 Correct 12 ms 23812 KB Output is correct
11 Correct 12 ms 23828 KB Output is correct
12 Correct 12 ms 23804 KB Output is correct
13 Correct 12 ms 23836 KB Output is correct
14 Correct 12 ms 23756 KB Output is correct
15 Correct 12 ms 23812 KB Output is correct
16 Correct 12 ms 23776 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23772 KB Output is correct
2 Correct 12 ms 23816 KB Output is correct
3 Correct 13 ms 23824 KB Output is correct
4 Correct 13 ms 23756 KB Output is correct
5 Correct 12 ms 23812 KB Output is correct
6 Correct 12 ms 23780 KB Output is correct
7 Correct 13 ms 23756 KB Output is correct
8 Correct 14 ms 23756 KB Output is correct
9 Correct 14 ms 23756 KB Output is correct
10 Correct 12 ms 23812 KB Output is correct
11 Correct 12 ms 23828 KB Output is correct
12 Correct 12 ms 23804 KB Output is correct
13 Correct 12 ms 23836 KB Output is correct
14 Correct 12 ms 23756 KB Output is correct
15 Correct 12 ms 23812 KB Output is correct
16 Correct 12 ms 23776 KB Output is correct
17 Correct 16 ms 24140 KB Output is correct
18 Correct 14 ms 24268 KB Output is correct
19 Correct 14 ms 24176 KB Output is correct
20 Correct 15 ms 24140 KB Output is correct
21 Correct 14 ms 24212 KB Output is correct
22 Correct 20 ms 24048 KB Output is correct
23 Correct 16 ms 24140 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23772 KB Output is correct
2 Correct 12 ms 23816 KB Output is correct
3 Correct 13 ms 23824 KB Output is correct
4 Correct 13 ms 23756 KB Output is correct
5 Correct 12 ms 23812 KB Output is correct
6 Correct 12 ms 23780 KB Output is correct
7 Correct 13 ms 23756 KB Output is correct
8 Correct 14 ms 23756 KB Output is correct
9 Correct 14 ms 23756 KB Output is correct
10 Correct 12 ms 23812 KB Output is correct
11 Correct 12 ms 23828 KB Output is correct
12 Correct 12 ms 23804 KB Output is correct
13 Correct 12 ms 23836 KB Output is correct
14 Correct 12 ms 23756 KB Output is correct
15 Correct 12 ms 23812 KB Output is correct
16 Correct 12 ms 23776 KB Output is correct
17 Correct 16 ms 24140 KB Output is correct
18 Correct 14 ms 24268 KB Output is correct
19 Correct 14 ms 24176 KB Output is correct
20 Correct 15 ms 24140 KB Output is correct
21 Correct 14 ms 24212 KB Output is correct
22 Correct 20 ms 24048 KB Output is correct
23 Correct 16 ms 24140 KB Output is correct
24 Correct 171 ms 55288 KB Output is correct
25 Correct 253 ms 65744 KB Output is correct
26 Correct 169 ms 55600 KB Output is correct
27 Correct 319 ms 67312 KB Output is correct
28 Correct 215 ms 56324 KB Output is correct
29 Correct 174 ms 58156 KB Output is correct
30 Correct 370 ms 58620 KB Output is correct
31 Correct 108 ms 44660 KB Output is correct
32 Correct 97 ms 41608 KB Output is correct
33 Correct 253 ms 52464 KB Output is correct
34 Correct 332 ms 62524 KB Output is correct
35 Correct 338 ms 52436 KB Output is correct
36 Correct 315 ms 52104 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23772 KB Output is correct
2 Correct 12 ms 23816 KB Output is correct
3 Correct 13 ms 23824 KB Output is correct
4 Correct 13 ms 23756 KB Output is correct
5 Correct 12 ms 23812 KB Output is correct
6 Correct 12 ms 23780 KB Output is correct
7 Correct 13 ms 23756 KB Output is correct
8 Correct 14 ms 23756 KB Output is correct
9 Correct 14 ms 23756 KB Output is correct
10 Correct 12 ms 23812 KB Output is correct
11 Correct 12 ms 23828 KB Output is correct
12 Correct 12 ms 23804 KB Output is correct
13 Correct 12 ms 23836 KB Output is correct
14 Correct 12 ms 23756 KB Output is correct
15 Correct 12 ms 23812 KB Output is correct
16 Correct 12 ms 23776 KB Output is correct
17 Correct 16 ms 24140 KB Output is correct
18 Correct 14 ms 24268 KB Output is correct
19 Correct 14 ms 24176 KB Output is correct
20 Correct 15 ms 24140 KB Output is correct
21 Correct 14 ms 24212 KB Output is correct
22 Correct 20 ms 24048 KB Output is correct
23 Correct 16 ms 24140 KB Output is correct
24 Correct 171 ms 55288 KB Output is correct
25 Correct 253 ms 65744 KB Output is correct
26 Correct 169 ms 55600 KB Output is correct
27 Correct 319 ms 67312 KB Output is correct
28 Correct 215 ms 56324 KB Output is correct
29 Correct 174 ms 58156 KB Output is correct
30 Correct 370 ms 58620 KB Output is correct
31 Correct 108 ms 44660 KB Output is correct
32 Correct 97 ms 41608 KB Output is correct
33 Correct 253 ms 52464 KB Output is correct
34 Correct 332 ms 62524 KB Output is correct
35 Correct 338 ms 52436 KB Output is correct
36 Correct 315 ms 52104 KB Output is correct
37 Correct 195 ms 58524 KB Output is correct
38 Correct 269 ms 70360 KB Output is correct
39 Correct 289 ms 69324 KB Output is correct
40 Correct 195 ms 56944 KB Output is correct
41 Correct 12 ms 23756 KB Output is correct
42 Correct 428 ms 61680 KB Output is correct
43 Correct 271 ms 55364 KB Output is correct
44 Correct 336 ms 65352 KB Output is correct
45 Correct 372 ms 55460 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23772 KB Output is correct
2 Correct 12 ms 23816 KB Output is correct
3 Correct 13 ms 23824 KB Output is correct
4 Correct 13 ms 23756 KB Output is correct
5 Correct 12 ms 23812 KB Output is correct
6 Correct 12 ms 23780 KB Output is correct
7 Correct 13 ms 23756 KB Output is correct
8 Correct 14 ms 23756 KB Output is correct
9 Correct 14 ms 23756 KB Output is correct
10 Correct 12 ms 23812 KB Output is correct
11 Correct 12 ms 23828 KB Output is correct
12 Correct 12 ms 23804 KB Output is correct
13 Correct 12 ms 23836 KB Output is correct
14 Correct 12 ms 23756 KB Output is correct
15 Correct 12 ms 23812 KB Output is correct
16 Correct 12 ms 23776 KB Output is correct
17 Correct 16 ms 24140 KB Output is correct
18 Correct 14 ms 24268 KB Output is correct
19 Correct 14 ms 24176 KB Output is correct
20 Correct 15 ms 24140 KB Output is correct
21 Correct 14 ms 24212 KB Output is correct
22 Correct 20 ms 24048 KB Output is correct
23 Correct 16 ms 24140 KB Output is correct
24 Correct 171 ms 55288 KB Output is correct
25 Correct 253 ms 65744 KB Output is correct
26 Correct 169 ms 55600 KB Output is correct
27 Correct 319 ms 67312 KB Output is correct
28 Correct 215 ms 56324 KB Output is correct
29 Correct 174 ms 58156 KB Output is correct
30 Correct 370 ms 58620 KB Output is correct
31 Correct 108 ms 44660 KB Output is correct
32 Correct 97 ms 41608 KB Output is correct
33 Correct 253 ms 52464 KB Output is correct
34 Correct 332 ms 62524 KB Output is correct
35 Correct 338 ms 52436 KB Output is correct
36 Correct 315 ms 52104 KB Output is correct
37 Correct 195 ms 58524 KB Output is correct
38 Correct 269 ms 70360 KB Output is correct
39 Correct 289 ms 69324 KB Output is correct
40 Correct 195 ms 56944 KB Output is correct
41 Correct 12 ms 23756 KB Output is correct
42 Correct 428 ms 61680 KB Output is correct
43 Correct 271 ms 55364 KB Output is correct
44 Correct 336 ms 65352 KB Output is correct
45 Correct 372 ms 55460 KB Output is correct
46 Correct 954 ms 195912 KB Output is correct
47 Correct 1442 ms 257932 KB Output is correct
48 Correct 1526 ms 252076 KB Output is correct
49 Correct 910 ms 189816 KB Output is correct
50 Correct 2521 ms 214804 KB Output is correct
51 Correct 1462 ms 178976 KB Output is correct
52 Correct 2174 ms 226320 KB Output is correct
53 Correct 2239 ms 182512 KB Output is correct

Subtask #7
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 57412 KB Output is correct
2 Correct 225 ms 46928 KB Output is correct
3 Correct 198 ms 60216 KB Output is correct
4 Correct 253 ms 63348 KB Output is correct
5 Correct 12 ms 23776 KB Output is correct
6 Correct 224 ms 59512 KB Output is correct
7 Correct 86 ms 41148 KB Output is correct
8 Correct 108 ms 43332 KB Output is correct
9 Correct 190 ms 61256 KB Output is correct
10 Correct 182 ms 53276 KB Output is correct
11 Correct 140 ms 54592 KB Output is correct
12 Correct 12 ms 23772 KB Output is correct
13 Correct 12 ms 23816 KB Output is correct
14 Correct 13 ms 23824 KB Output is correct
15 Correct 13 ms 23756 KB Output is correct
16 Correct 12 ms 23812 KB Output is correct
17 Correct 12 ms 23780 KB Output is correct
18 Correct 13 ms 23756 KB Output is correct
19 Correct 14 ms 23756 KB Output is correct
20 Correct 14 ms 23756 KB Output is correct
21 Correct 12 ms 23812 KB Output is correct
22 Correct 12 ms 23828 KB Output is correct
23 Correct 12 ms 23804 KB Output is correct
24 Correct 12 ms 23836 KB Output is correct
25 Correct 12 ms 23756 KB Output is correct
26 Correct 12 ms 23812 KB Output is correct
27 Correct 12 ms 23776 KB Output is correct
28 Correct 16 ms 24140 KB Output is correct
29 Correct 14 ms 24268 KB Output is correct
30 Correct 14 ms 24176 KB Output is correct
31 Correct 15 ms 24140 KB Output is correct
32 Correct 14 ms 24212 KB Output is correct
33 Correct 20 ms 24048 KB Output is correct
34 Correct 16 ms 24140 KB Output is correct
35 Correct 171 ms 55288 KB Output is correct
36 Correct 253 ms 65744 KB Output is correct
37 Correct 169 ms 55600 KB Output is correct
38 Correct 319 ms 67312 KB Output is correct
39 Correct 215 ms 56324 KB Output is correct
40 Correct 174 ms 58156 KB Output is correct
41 Correct 370 ms 58620 KB Output is correct
42 Correct 108 ms 44660 KB Output is correct
43 Correct 97 ms 41608 KB Output is correct
44 Correct 253 ms 52464 KB Output is correct
45 Correct 332 ms 62524 KB Output is correct
46 Correct 338 ms 52436 KB Output is correct
47 Correct 315 ms 52104 KB Output is correct
48 Correct 195 ms 58524 KB Output is correct
49 Correct 269 ms 70360 KB Output is correct
50 Correct 289 ms 69324 KB Output is correct
51 Correct 195 ms 56944 KB Output is correct
52 Correct 12 ms 23756 KB Output is correct
53 Correct 428 ms 61680 KB Output is correct
54 Correct 271 ms 55364 KB Output is correct
55 Correct 336 ms 65352 KB Output is correct
56 Correct 372 ms 55460 KB Output is correct
57 Correct 268 ms 70828 KB Output is correct
58 Correct 208 ms 58316 KB Output is correct
59 Correct 232 ms 57888 KB Output is correct
60 Correct 305 ms 70308 KB Output is correct
61 Correct 298 ms 58912 KB Output is correct
62 Correct 12 ms 23756 KB Output is correct
63 Correct 411 ms 61928 KB Output is correct
64 Correct 272 ms 55260 KB Output is correct
65 Correct 353 ms 61044 KB Output is correct
66 Correct 345 ms 55408 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 57412 KB Output is correct
2 Correct 225 ms 46928 KB Output is correct
3 Correct 198 ms 60216 KB Output is correct
4 Correct 253 ms 63348 KB Output is correct
5 Correct 12 ms 23776 KB Output is correct
6 Correct 224 ms 59512 KB Output is correct
7 Correct 86 ms 41148 KB Output is correct
8 Correct 108 ms 43332 KB Output is correct
9 Correct 190 ms 61256 KB Output is correct
10 Correct 182 ms 53276 KB Output is correct
11 Correct 140 ms 54592 KB Output is correct
12 Correct 12 ms 23772 KB Output is correct
13 Correct 12 ms 23816 KB Output is correct
14 Correct 13 ms 23824 KB Output is correct
15 Correct 13 ms 23756 KB Output is correct
16 Correct 12 ms 23812 KB Output is correct
17 Correct 12 ms 23780 KB Output is correct
18 Correct 13 ms 23756 KB Output is correct
19 Correct 14 ms 23756 KB Output is correct
20 Correct 14 ms 23756 KB Output is correct
21 Correct 12 ms 23812 KB Output is correct
22 Correct 12 ms 23828 KB Output is correct
23 Correct 12 ms 23804 KB Output is correct
24 Correct 12 ms 23836 KB Output is correct
25 Correct 12 ms 23756 KB Output is correct
26 Correct 12 ms 23812 KB Output is correct
27 Correct 12 ms 23776 KB Output is correct
28 Correct 16 ms 24140 KB Output is correct
29 Correct 14 ms 24268 KB Output is correct
30 Correct 14 ms 24176 KB Output is correct
31 Correct 15 ms 24140 KB Output is correct
32 Correct 14 ms 24212 KB Output is correct
33 Correct 20 ms 24048 KB Output is correct
34 Correct 16 ms 24140 KB Output is correct
35 Correct 171 ms 55288 KB Output is correct
36 Correct 253 ms 65744 KB Output is correct
37 Correct 169 ms 55600 KB Output is correct
38 Correct 319 ms 67312 KB Output is correct
39 Correct 215 ms 56324 KB Output is correct
40 Correct 174 ms 58156 KB Output is correct
41 Correct 370 ms 58620 KB Output is correct
42 Correct 108 ms 44660 KB Output is correct
43 Correct 97 ms 41608 KB Output is correct
44 Correct 253 ms 52464 KB Output is correct
45 Correct 332 ms 62524 KB Output is correct
46 Correct 338 ms 52436 KB Output is correct
47 Correct 315 ms 52104 KB Output is correct
48 Correct 195 ms 58524 KB Output is correct
49 Correct 269 ms 70360 KB Output is correct
50 Correct 289 ms 69324 KB Output is correct
51 Correct 195 ms 56944 KB Output is correct
52 Correct 12 ms 23756 KB Output is correct
53 Correct 428 ms 61680 KB Output is correct
54 Correct 271 ms 55364 KB Output is correct
55 Correct 336 ms 65352 KB Output is correct
56 Correct 372 ms 55460 KB Output is correct
57 Correct 954 ms 195912 KB Output is correct
58 Correct 1442 ms 257932 KB Output is correct
59 Correct 1526 ms 252076 KB Output is correct
60 Correct 910 ms 189816 KB Output is correct
61 Correct 2521 ms 214804 KB Output is correct
62 Correct 1462 ms 178976 KB Output is correct
63 Correct 2174 ms 226320 KB Output is correct
64 Correct 2239 ms 182512 KB Output is correct
65 Correct 268 ms 70828 KB Output is correct
66 Correct 208 ms 58316 KB Output is correct
67 Correct 232 ms 57888 KB Output is correct
68 Correct 305 ms 70308 KB Output is correct
69 Correct 298 ms 58912 KB Output is correct
70 Correct 12 ms 23756 KB Output is correct
71 Correct 411 ms 61928 KB Output is correct
72 Correct 272 ms 55260 KB Output is correct
73 Correct 353 ms 61044 KB Output is correct
74 Correct 345 ms 55408 KB Output is correct
75 Correct 1374 ms 259600 KB Output is correct
76 Correct 1006 ms 197264 KB Output is correct
77 Correct 994 ms 191932 KB Output is correct
78 Correct 1536 ms 254000 KB Output is correct
79 Correct 2540 ms 215256 KB Output is correct
80 Correct 1459 ms 179724 KB Output is correct
81 Correct 1931 ms 205708 KB Output is correct
82 Correct 2273 ms 182832 KB Output is correct
83 Correct 2431 ms 200992 KB Output is correct