Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2010
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2010
Keep it Energized
By Fidel I. Schaposnik Massolo 
Argentina
Timelimit: 5
The Incredible Consoles Production Company (ICPC) is now designing its newest video game console model, the Super-Arcade Reloaded (SAR). The launch of the SAR will be accompanied by the release of a flagship game, which will only be available to its users. This game, which incidentally shall be called Adventures of Captain Mikado (ACM), even features an in-game currency which can be conveniently bought using real-world money!
The ACM is a very simple game consisting of N levels numbered 1, 2, . . . , N, the i-th level requiring exactly Ei units of energy to be completed. This means that in order to complete that level, the user’s energy should be at least Ei , and after doing so it will decrease in exactly that amount. To win the game the user should complete all the levels in increasing order, starting at level 1 and continuing until level N without ever going back to some already-completed level.
Initially the user starts with no energy, and in order to get some he must buy energy packs from the ingame shops distributed among the N levels. There are M such shops. Each shop sells an energy pack having a strength S and a cost C that depend on the shop. The user can only buy energy packs from the shops in the level he is currently in, before starting to complete that level. The effect of buying an energy pack of strength S is that the user’s energy immediately turns into S, regardless of which value it had before.
In order to increase even further its sales, the ICPC has thought of a revolutionary promotion: it will reimburse the full cost of the SAR to whoever completes the ACM game using the minimum amount of in-game cash. Given the description of the game, can you help them find out what is the minimum amount of in-game cash required to finish the game?
Input
The input contains several test cases; each test case is formatted as follows. The first line contains two integers N and M, representing respectively the number of levels and the number of shops in the game (1 ≤ N, M ≤ 105 ). The second line contains N integers E1, E2, . . . , EN , where Ei is the energy required to complete the i-th level (1 ≤ Ei ≤ 104 for i = 1, 2, . . . , N). Each of the next M lines describes a shop with three integers L, S and C, representing respectively the level where the shop is located, and the strength and cost of the energy pack it sells (1 ≤ L ≤ N, 1 ≤ S ≤ 109 and 1 ≤ C ≤ 104 ).
Output
For each test case in the input, output a line with an integer representing the minimum amount of in-game cash that is required to complete all N levels in the game. If it is impossible to complete all the levels, write the value ‘-1’.
| Input Samples | Output Samples |
|
5 4 1 2 3 4 5 1 6 5 2 14 10 5 5 4 3 7 5 |
14 |
|
3 4 14 11 2015 1 14 23 2 11 9 3 1987 1 1 2039 33 |
-1 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
typedef tuple < int, int, int> trinca;
const int MAXN = 1e5 + 10;
const int INF = 1e9 + 1e8;
int seg[4 * MAXN], lazy[4 * MAXN], n, m;
vector < trinca> lojas;
vector<int> prefixo;
void propagate(int pos, int left, int right) {
if (lazy[pos] == INF) return;
seg[pos] = min(seg[pos], lazy[pos]);
if (left != right) {
lazy[2 * pos] = min(lazy[2 * pos], lazy[pos]);
lazy[2 * pos + 1] = min(lazy[2 * pos + 1], lazy[pos]);
}
lazy[pos] = INF;
}
void update(int pos, int left, int right, int i, int j, int val) {
if (left > right || left > j || right < i) return;
if (left >= i && right <= j) {
lazy[pos] = min(lazy[pos], val);
propagate(pos, left, right);
return;
}
int mid = (left + right) / 2;
update(2 * pos, left, mid, i, j, val);
update(2 * pos + 1, mid + 1, right, i, j, val);
seg[pos] = min(seg[2 * pos], seg[2 * pos + 1]);
}
int get(int pos, int left, int right, int alvo) {
propagate(pos, left, right);
if (left == right) return seg[pos];
int mid = (left + right) / 2;
if (alvo < = mid) return get(2 * pos, left, mid, alvo);
return get(2 * pos + 1, mid + 1, right, alvo);
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
cin >> n >> m;
prefixo.push_back(0);
for (int i = 1; i < = 4 * n + 8; i++) {
seg[i] = lazy[i] = INF;
}
update(1, 0, n, 0, 0, 0);
for (int i = 1; i < = n; i++) {
int x;
cin >> x;
prefixo.push_back(prefixo.back() + x);
}
for (int i = 1; i < = m; i++) {
int l, n, s;
cin >> l >> n >> s;
lojas.push_back(make_tuple(l, n, s));
}
sort(lojas.begin(), lojas.end());
for (int i = 0; i < lojas.size(); i++) {
int pos = get<0>(lojas[i]), forca = get<1>(lojas[i]),
preco = get<2>(lojas[i]);
int real = preco + get(1, 0, n, pos - 1);
int alcanca = prev(upper_bound(prefixo.begin(), prefixo.end(),
prefixo[pos - 1] + forca)) -
prefixo.begin();
if (pos < = alcanca) update(1, 0, n, pos, alcanca, real);
}
int resp = get(1, 0, n, n);
if (resp == INF) resp = -1;
cout << resp << endl;
return 0;
}
Input
1 2 3 4 5
1 6 5
2 14 10
5 5 4
3 7 5
Output