Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <string>
- #include <vector>
- #include <algorithm>
- #include <set>
- #include <map>
- #include <cmath>
- #include <ctime>
- #include <functional>
- #include <sstream>
- #include <fstream>
- #include <valarray>
- #include <complex>
- #include <queue>
- #include <cassert>
- #include <bitset>
- using namespace std;
- #ifdef LOCAL
- #define debug_flag 1
- #else
- #define debug_flag 0
- #endif
- template <class T1, class T2 >
- std::ostream& operator << (std::ostream& os, const pair<T1, T2> &p)
- {
- os << "[" << p.first << ", " << p.second << "]";
- return os;
- }
- template <class T >
- std::ostream& operator << (std::ostream& os, const std::vector<T>& v)
- {
- os << "[";
- bool first = true;
- for (typename std::vector<T>::const_iterator it = v.begin(); it != v.end(); ++it)
- {
- if (!first)
- os << ", ";
- first = false;
- os << *it;
- }
- os << "]";
- return os;
- }
- #define dbg(args...) { if (debug_flag) { _print(_split(#args, ',').begin(), args); cerr << endl; } else { void(0);} }
- vector<string> _split(const string& s, char c) {
- vector<string> v;
- stringstream ss(s);
- string x;
- while (getline(ss, x, c))
- v.emplace_back(x);
- return v;
- }
- void _print(vector<string>::iterator) {}
- template<typename T, typename... Args>
- void _print(vector<string>::iterator it, T a, Args... args) {
- string name = it -> substr((*it)[0] == ' ', it -> length());
- if (isalpha(name[0]))
- cerr << name << " = " << a << " ";
- else
- cerr << name << " ";
- _print(++it, args...);
- }
- typedef long long int int64;
- const int64 int64_INF = (int64)1e18;
- namespace Slow
- {
- int n;
- vector<int64> p_list;
- vector<int> d_list;
- int64 best_ans;
- set<vector<int64> > used;
- bool are_all_same(const vector<int> & l)
- {
- for (int i = 1; i < (int)l.size(); i++)
- if (l[0] != l[i])
- return false;
- return true;
- }
- vector<int64> get_state(int64 cur_ans, vector<int> colors, vector<int> cur_dist)
- {
- vector<int64> state;
- state.push_back(cur_ans);
- for (int64 x : colors)
- state.push_back(x);
- for (int64 x : cur_dist)
- state.push_back(x);
- return state;
- }
- void rec(int64 cur_ans, vector<int> colors, vector<int> cur_d_list)
- {
- if (cur_ans >= best_ans)
- return;
- vector<int64> state = get_state(cur_ans, colors, cur_d_list);
- if (used.count(state) == 1)
- return;
- used.insert(state);
- if (are_all_same(colors))
- {
- best_ans = min(best_ans, cur_ans);
- return;
- }
- for (int i = 0; i < n; i++)
- {
- for (int j = i + 1; j < n; j++)
- {
- if (colors[i] != colors[j] && cur_d_list[i] >= 1 && cur_d_list[j] >= 1)
- {
- cur_d_list[i]--;
- cur_d_list[j]--;
- vector<int> new_colors = colors;
- int x = colors[i];
- int y = colors[j];
- for (int & c : new_colors)
- if (c == x)
- c = y;
- rec(cur_ans + abs(p_list[i] - p_list[j]), new_colors, cur_d_list);
- cur_d_list[i]++;
- cur_d_list[j]++;
- }
- }
- }
- }
- int64 solve(int _n, vector<int64> _p_list, vector<int> _d_list)
- {
- n = _n;
- p_list = _p_list;
- d_list = _d_list;
- best_ans = int64_INF;
- vector<int> colors(n);
- for (int i = 0; i < n; i++)
- colors[i] = i;
- rec(0, colors, d_list);
- if (best_ans == int64_INF)
- best_ans = -1;
- return best_ans;
- }
- };
- namespace Fast
- {
- int n;
- vector<int64> p_list;
- vector<int> d_list;
- bool cmp_by_p(int a, int b)
- {
- return p_list[a] < p_list[b];
- }
- int64 get_dist(int a, int b)
- {
- return abs(p_list[a] - p_list[b]);
- }
- int64 solve(int _n, vector<int64> _p_list, vector<int> _d_list)
- {
- n = _n;
- p_list = _p_list;
- d_list = _d_list;
- if (n <= 2)
- {
- return Slow::solve(n, p_list, d_list);
- }
- vector<int> small_list;
- vector<int> big_list;
- for (int i = 0; i < n; i++)
- {
- if (d_list[i] == 1)
- {
- small_list.push_back(i);
- }
- else
- {
- big_list.push_back(i);
- }
- }
- int small_size = (int)small_list.size();
- int big_size = (int)big_list.size();
- sort(small_list.begin(), small_list.end(), cmp_by_p);
- sort(big_list.begin(), big_list.end(), cmp_by_p);
- if (big_size == 0)
- return -1;
- int64 ans0 = 0;
- for (int i = 0; i + 1 < big_size; i++)
- {
- int a = big_list[i];
- int b = big_list[i + 1];
- if (d_list[a] == 0 || d_list[b] == 0)
- return -1;
- d_list[a]--;
- d_list[b]--;
- ans0 += get_dist(a, b);
- }
- dbg(ans0);
- dbg(small_list);
- dbg(big_list);
- dbg("d_list after", d_list);
- vector<int64> dp(small_size + 1, int64_INF);
- dp[0] = 0;
- for (int i = 0; i < (int)big_list.size(); i++)
- {
- vector<int64> new_dp = dp;
- for (int j = 1; j <= small_size; j++)
- {
- int l = max(1, j - d_list[i] + 1);
- int r = j;
- int64 sum = 0;
- for (int t = r; t >= l; t--)
- {
- sum += get_dist(big_list[i], small_list[t - 1]);
- int64 cur_val = sum + dp[t - 1];
- new_dp[j] = min(new_dp[j], cur_val);
- }
- }
- dp = new_dp;
- }
- int64 ans1 = dp[small_size];
- if (ans1 == int64_INF)
- return -1;
- return ans0 + ans1;
- }
- };
- void submit()
- {
- int n;
- scanf("%d", &n);
- vector<int64> p_list(n);
- vector<int> d_list(n);
- for (int i = 0; i < n; i++)
- {
- scanf("%lld%d", &p_list[i], &d_list[i]);
- }
- int64 ans = Slow::solve(n, p_list, d_list);
- printf("%lld\n", ans);
- }
- void stress()
- {
- const int IT = 1e5;
- const int N = 3;
- const int P = 3;
- const int D = 3;
- for (int it = 0; it < IT; it++)
- {
- printf("it = %d\n", it);
- int n = rand() % N + 1;
- vector<int64> p_list(n);
- vector<int> d_list(n);
- for (int i = 0; i < n; i++)
- {
- p_list[i] = rand() % P + 1;
- d_list[i] = rand() % D + 1;
- }
- int64 fast_ans = Fast::solve(n, p_list, d_list);
- int64 slow_ans = Slow::solve(n, p_list, d_list);
- if (fast_ans != slow_ans)
- {
- printf("fast_ans = %lld slow_ans = %lld\n", fast_ans, slow_ans);
- printf("%d\n", n);
- for (int i = 0; i < n; i++)
- {
- printf("%lld %d\n", p_list[i], d_list[i]);
- }
- return;
- }
- }
- printf("stress passed\n");
- }
- int main()
- {
- #ifdef LOCAL
- freopen ("input.txt", "r", stdin);
- #endif
- submit();
- //stress();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement