oj.uz

Submission #409500

# Submission time Handle Problem Language Result Execution time Memory
409500 2021-05-21T00:29:44 Z 534351 Dungeon 3 (JOI21_ho_t5) C++17
11 / 100
 4000 ms 5976 KB 
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)

const int MAXN = 2e5 + 13;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, Q;
ll A[MAXN], B[MAXN];

int32_t main()
{
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(4);
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N >> Q;
    FOR(i, 0, N)
    {
        cin >> A[i];
    }
    FOR(i, 0, N)
    {
        cin >> B[i];
    }
    while(Q--)
    {
        int l, r; ll k, ans = 0;
        cin >> l >> r >> k;
        l--; r -= 2;
        ll c = 0;
        //cost, how much you have of it.
        set<pll> s; ll tot = 0;
        FOR(i, l, r + 1)
        {
            ll cnt = A[i], cost = B[i];
            if (cnt > k)
            {
                ans = -1;
                break;
            }
            s.insert({cost, k});
            tot += k;
            //find out minimum # of money it takes to raise cnt.
            while(cnt > 0)
            {
                auto p = *s.begin(); s.erase(s.begin());
                ll num = min(p.se, cnt);
                cnt -= num;
                tot -= num;
                p.se -= num;
                if (p.se != 0)
                {
                    s.insert(p);
                }
                // cerr << "+= " << p.fi << '*' << num << endl;
                ans += p.fi * num;
            }
            cnt = k - A[i];
            while(tot > cnt)
            {
                auto p = *prev(s.end()); s.erase(prev(s.end()));
                ll num = min(p.se, tot - cnt);
                tot -= num;
                p.se -= num;
                if (p.se != 0)
                {
                    s.insert(p);
                }
            }
            //after this collection, you're only allowed to have k-cnt.
            // cerr << "cnt " << cnt << " cost " << cost << endl;
            // if (cnt > k)
            // {
            //     ans = -1;
            //     break;
            // }
            // c += cnt;
            // //you have to pay off the excess over k.
            // while(c > k)
            // {
            //     auto p = *s.begin();
            //     s.erase(s.begin());
            //     ll take = min(c - k, p.fi);
            //     ans += p.fi * take;
            //     c -= take;
            //     p.se -= take;
            //     if (p.se > 0) s.insert(p);
            // }
            // s.insert({cost, c});
            //now cost has to be > k?
        }
        cout << ans << '\n';
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:61:12: warning: unused variable 'c' [-Wunused-variable]
   61 |         ll c = 0;
      |            ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 629 ms 484 KB Output is correct
2 Correct 760 ms 652 KB Output is correct
3 Correct 423 ms 456 KB Output is correct
4 Correct 707 ms 464 KB Output is correct
5 Correct 754 ms 708 KB Output is correct
6 Correct 403 ms 592 KB Output is correct
7 Correct 698 ms 476 KB Output is correct
8 Correct 724 ms 708 KB Output is correct
9 Correct 453 ms 460 KB Output is correct
10 Correct 650 ms 600 KB Output is correct
11 Correct 670 ms 580 KB Output is correct
12 Correct 377 ms 604 KB Output is correct
13 Correct 668 ms 612 KB Output is correct
14 Correct 454 ms 472 KB Output is correct
15 Correct 468 ms 440 KB Output is correct
16 Correct 727 ms 836 KB Output is correct
17 Correct 449 ms 480 KB Output is correct
18 Correct 483 ms 600 KB Output is correct
19 Correct 277 ms 580 KB Output is correct
20 Correct 2232 ms 688 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4066 ms 2116 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4057 ms 5976 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 629 ms 484 KB Output is correct
2 Correct 760 ms 652 KB Output is correct
3 Correct 423 ms 456 KB Output is correct
4 Correct 707 ms 464 KB Output is correct
5 Correct 754 ms 708 KB Output is correct
6 Correct 403 ms 592 KB Output is correct
7 Correct 698 ms 476 KB Output is correct
8 Correct 724 ms 708 KB Output is correct
9 Correct 453 ms 460 KB Output is correct
10 Correct 650 ms 600 KB Output is correct
11 Correct 670 ms 580 KB Output is correct
12 Correct 377 ms 604 KB Output is correct
13 Correct 668 ms 612 KB Output is correct
14 Correct 454 ms 472 KB Output is correct
15 Correct 468 ms 440 KB Output is correct
16 Correct 727 ms 836 KB Output is correct
17 Correct 449 ms 480 KB Output is correct
18 Correct 483 ms 600 KB Output is correct
19 Correct 277 ms 580 KB Output is correct
20 Correct 2232 ms 688 KB Output is correct
21 Execution timed out 4066 ms 2116 KB Time limit exceeded
22 Halted 0 ms 0 KB -