Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #ifdef NOT_DMOJ
- //secret header that provides answers to all questions
- #include"contest includes.h"
- #else
- //include everything header for GCC
- #include<bits/stdc++.h>
- #endif
- #pragma region template code
- using namespace std;
- template<typename T>using minheap = priority_queue<T, vector<T>, greater<T>>;
- template<typename T>using maxheap = priority_queue<T>;
- template<typename T>using dpair = pair<T, T>;
- typedef long long ll;
- typedef dpair<int> pii;
- typedef dpair<long long> pll;
- typedef dpair<float> pff;
- typedef dpair<double> pdd;
- template<class T1, class T2>
- istream& operator >> (istream &is, pair<T1, T2> &p) {
- return is >> p.first >> p.second;
- }
- template<class T1, class T2>
- ostream& operator << (ostream &os, pair<T1, T2> &p) {
- return os << "<" << p.first << ", " << p.second << ">";
- }
- template<class T1, class T2>
- void operator+=(vector<T1> &v, const T2 &obj) {
- v.push_back(obj);
- }
- template<class T1>
- void operator+=(vector<T1> &v, const T1 &obj) {
- v.push_back(obj);
- }
- const int INF = 0x3f3f3f3f;
- const ll mod = 1e9 + 7;
- class range {
- public:
- range(int end) :_start(0), _end(end), _step(1) {}
- range(int start, int end) :_start(start), _end(end), _step(1) {}
- range(int start, int end, int step) :_start(start), _end(end), _step(step) {}
- class iterator {
- public: iterator(int v, int s) :val(v), step(s) {};
- int operator*() const {
- return val;
- } int operator++() {
- return (val += step);
- } bool operator==(const range::iterator &iter) const {
- return val == iter.val && step == iter.step;
- } bool operator!=(const range::iterator &iter) const {
- return !(this->operator==(iter));
- } private: int val;
- int step;
- };
- range::iterator begin() {
- return{ _start, _step };
- }
- range::iterator end() {
- return{ _end, _step };
- }
- private:
- int _start, _end, _step;
- };
- #pragma endregion
- const int MAXN = 2005;
- ll dp[2][MAXN][MAXN];
- vector<pll> possugar;
- vector<pll> negsugar;
- ll init_energy;
- ll sumpos[MAXN];
- ll sumneg[MAXN];
- int main() {
- #ifdef NOT_DMOJ
- freopen("text.txt", "r", stdin);
- #else
- cin.tie(0);
- cin.sync_with_stdio(0);
- #endif
- int N;
- cin >> N;
- for (int a = 0; a < N; a++) {
- pll p;
- cin >> p;
- if (p.first == 0) {
- init_energy = p.second;
- } else if (p.first > 0) {
- possugar.push_back(p);
- } else if( p.first < 0){
- p.first *= -1;
- negsugar.push_back(p);
- }
- }
- possugar.push_back({ 0,init_energy });
- negsugar.push_back({ 0,0 });
- sort(possugar.begin(), possugar.end());
- sort(negsugar.begin(), negsugar.end());
- for (int a = 0; a < possugar.size(); a++) {
- sumpos[a + 1] = sumpos[a] + possugar[a].second;
- }
- for (int a = 0; a < negsugar.size(); a++) {
- sumneg[a + 1] = sumneg[a] + negsugar[a].second;
- }
- //min distance to
- for (int a = 0; a < MAXN; a++) {
- for (int b = 0; b < MAXN; b++) {
- dp[0][a][b] = 1e15;
- dp[1][a][b] = 1e15;
- }
- }
- dp[0][0][0] = dp[1][0][0] = 0;
- for (int a = 0; a < possugar.size(); a++) {
- for (int b = 0; b < negsugar.size(); b++) {
- ll totsugar = sumpos[a + 1] + sumneg[b + 1];
- //dp[0] pos side
- //continue positive
- if (a != possugar.size() - 1 &&
- totsugar - dp[0][a][b] >= possugar[a + 1].first - possugar[a].first) {
- dp[0][a + 1][b] = min(dp[0][a + 1][b], dp[0][a][b] +
- possugar[a + 1].first - possugar[a].first);
- }
- //go negative side
- if (b != negsugar.size() - 1 &&
- totsugar - dp[0][a][b] >= possugar[a].first + negsugar[b + 1].first) {
- dp[1][a][b+1] = min(dp[1][a][b + 1], dp[0][a][b] +
- possugar[a].first + negsugar[b + 1].first);
- }
- //dp[1] neg side
- //go positive side
- if (a != possugar.size() - 1 &&
- totsugar - dp[1][a][b] >= possugar[a + 1].first + negsugar[b].first) {
- dp[0][a + 1][b] = min(dp[0][a + 1][b], dp[1][a][b] +
- possugar[a + 1].first + negsugar[b].first);
- }
- if (b != negsugar.size() - 1 &&
- totsugar - dp[1][a][b] >= negsugar[b+1].first - negsugar[b].first) {
- dp[1][a][b + 1] = min(dp[1][a][b + 1], dp[1][a][b] +
- negsugar[b + 1].first - negsugar[b].first);
- }
- }
- }
- ll ans = 0;
- for (int a = 0; a < possugar.size(); a++) {
- for (int b = 0; b < negsugar.size(); b++) {
- if (dp[0][a][b] != 1e15 || dp[1][a][b] != 1e15) {
- ans = max(ans, sumpos[a + 1] + sumneg[b + 1]);
- }
- }
- }
- cout << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement