Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <string>
- #include <set>
- #include <map>
- using namespace std;
- #define x first
- #define y second
- #define all(v) v.begin(), v.end()
- #define int long long
- struct line
- {
- int k, b;
- line() {k = 0; b = 0;}
- line(int K, int B) {k = K; b = B;}
- };
- int intersect(line f, line s)
- {
- return (f.b - s.b + s.k - f.k + 1) / (s.k - f.k);
- }
- class cht
- {
- public:
- vector<line> a;
- vector<int> g;
- int i;
- void add(line l)
- {
- while(1)
- {
- if(a.size() == 0)
- {
- a.push_back(l);
- g.push_back(0);
- return;
- }
- if(l.k == a.rbegin()->k)
- {
- if(l.b >= a.rbegin()->b) return;
- a.pop_back();
- g.pop_back();
- continue;
- }
- if(intersect(l, *a.rbegin()) <= *g.rbegin())
- {
- a.pop_back();
- g.pop_back();
- continue;
- }
- g.push_back(intersect(l, *a.rbegin()));
- a.push_back(l);
- return;
- }
- }
- int get(int x)
- {
- if(a.size() == 0) return 1e18 + 1;
- x--;
- for(i = 0; i < a.size(); i++)
- {
- if(g[i] > x) break;
- }
- i--;
- return x * a[i].k + a[i].b;
- }
- };
- int32_t main()
- {
- int n;
- cin >> n;
- vector<cht> a(5);
- int tmp1, tmp2, tmp3;
- int ans;
- for(int i = 0; i < n; i++)
- {
- ans = 1e9;
- cin >> tmp1 >> tmp2 >> tmp3;
- a[i % 5].add(line(tmp2, tmp1));
- for(int j = 0; j < 5; j++) ans = min(ans, a[j].get(tmp3));
- cout << ans << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement