Submission #639858

#TimeUsernameProblemLanguageResultExecution timeMemory
639858IWTIMWiring (IOI17_wiring)C++17
100 / 100
37 ms10564 KiB
# include "wiring.h" # include <bits/stdc++.h> using namespace std; using ll = long long; using db = long double; // or double, if TL is tight using str = string; // yay python! // pairs using pii = pair<int,int>; using pl = pair<ll,ll>; using pd = pair<db,db>; #define mp make_pair #define f first #define s second #define tcT template<class T #define tcTU tcT, class U // ^ lol this makes everything look weird but I'll try it tcT> using V = vector<T>; tcT, size_t SZ> using AR = array<T,SZ>; using vi = V<int>; using vb = V<bool>; using vl = V<ll>; using vd = V<db>; using vs = V<str>; using vpi = V<pii>; using vpl = V<pl>; using vpd = V<pd>; // vectors // oops size(x), rbegin(x), rend(x) need C++17 #define sz(x) int((x).size()) #define bg(x) begin(x) #define all(x) bg(x), end(x) #define rall(x) x.rbegin(), x.rend() #define sor(x) sort(all(x)) #define rsz resize #define ins insert #define pb push_back #define eb emplace_back #define ft front() #define bk back() #define lb lower_bound #define ub upper_bound #define FOR(i,a,b) for (int i = (a); i < (b); ++i) #define F0R(i,a) FOR(i,0,a) #define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i) #define R0F(i,a) ROF(i,0,a) #define rep(a) F0R(_,a) #define each(a,x) for (auto& a: x) const int MOD = 998244353; const int MX = 2e5+5; const ll BIG = 1e18; // not too close to LLONG_MAX const db PI = acos((db)-1); const int dx[4]{1,0,-1,0}, dy[4]{0,1,0,-1}; // for every grid problem!! mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>; struct DSU { vi e; void init(int N) { e = vi(N,-1); } int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); } bool sameSet(int a, int b) { return get(a) == get(b); } int size(int x) { return -e[get(x)]; } bool unite(int x, int y) { // union by size x = get(x), y = get(y); if (x == y) return 0; if (e[x] > e[y]) swap(x,y); e[x] += e[y]; e[y] = x; return 1; } }; /* inline namespace Helpers { //////////// is_iterable // https://stackoverflow.com/questions/13830158/check-if-a-variable-type-is-iterable // this gets used only when we can call begin() and end() on that type tcT, class = void> struct is_iterable : false_type {}; tcT> struct is_iterable<T, void_t<decltype(begin(declval<T>())), decltype(end(declval<T>())) > > : true_type {}; tcT> constexpr bool is_iterable_v = is_iterable<T>::value; //////////// is_readable tcT, class = void> struct is_readable : false_type {}; tcT> struct is_readable<T, typename std::enable_if_t< is_same_v<decltype(cin >> declval<T&>()), istream&> > > : true_type {}; tcT> constexpr bool is_readable_v = is_readable<T>::value; //////////// is_printable // // https://nafe.es/posts/2020-02-29-is-printable/ tcT, class = void> struct is_printable : false_type {}; tcT> struct is_printable<T, typename std::enable_if_t< is_same_v<decltype(cout << declval<T>()), ostream&> > > : true_type {}; tcT> constexpr bool is_printable_v = is_printable<T>::value; }*/ using ll = long long; using db = long double; // or double, if TL is tight using str = string; // yay python! // pairs using pii = pair<int,int>; using pl = pair<ll,ll>; using pd = pair<db,db>; #define mp make_pair #define f first #define s second #define tcT template<class T #define tcTU tcT, class U // ^ lol this makes everything look weird but I'll try it tcT> using V = vector<T>; tcT, size_t SZ> using AR = array<T,SZ>; using vi = V<int>; using vb = V<bool>; using vl = V<ll>; using vd = V<db>; using vs = V<str>; using vpi = V<pii>; using vpl = V<pl>; using vpd = V<pd>; // vectors // oops size(x), rbegin(x), rend(x) need C++17 #define sz(x) int((x).size()) #define bg(x) begin(x) #define all(x) bg(x), end(x) #define rall(x) x.rbegin(), x.rend() #define sor(x) sort(all(x)) #define rsz resize #define ins insert #define pb push_back #define eb emplace_back #define ft front() #define bk back() #define lb lower_bound #define ub upper_bound #define FOR(i,a,b) for (int i = (a); i < (b); ++i) #define F0R(i,a) FOR(i,0,a) #define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i) #define R0F(i,a) ROF(i,0,a) #define rep(a) F0R(_,a) #define each(a,x) for (auto& a: x) template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>; /* inline namespace Helpers { //////////// is_iterable // https://stackoverflow.com/questions/13830158/check-if-a-variable-type-is-iterable // this gets used only when we can call begin() and end() on that type tcT, class = void> struct is_iterable : false_type {}; tcT> struct is_iterable<T, void_t<decltype(begin(declval<T>())), decltype(end(declval<T>())) > > : true_type {}; tcT> constexpr bool is_iterable_v = is_iterable<T>::value; //////////// is_readable tcT, class = void> struct is_readable : false_type {}; tcT> struct is_readable<T, typename std::enable_if_t< is_same_v<decltype(cin >> declval<T&>()), istream&> > > : true_type {}; tcT> constexpr bool is_readable_v = is_readable<T>::value; //////////// is_printable // // https://nafe.es/posts/2020-02-29-is-printable/ tcT, class = void> struct is_printable : false_type {}; tcT> struct is_printable<T, typename std::enable_if_t< is_same_v<decltype(cout << declval<T>()), ostream&> > > : true_type {}; tcT> constexpr bool is_printable_v = is_printable<T>::value; }*/ const int N = 3e5 + 5; const long long inf = 1e15; long long a[N],dp[N],sf[N],pr[N]; long long min_total_length(std::vector<int> r, std::vector<int> b) { int n = r.size() + b.size(); int x = r.size(); int y = b.size(); int prty = -1; int curx = 0, cury = 0; int curty; vector < pii > seg; // Divide the combined array into blocks while (curx < x || cury < y) { //cout<<curx<<" "<<a[curx]<<" "<<cury<<" "<<b[cury]<<"\n"; if(curx >= x || (cury < y && b[cury] <= r[curx])) { a[curx + cury] = b[cury]; cury++; curty = 0; } else { a[curx + cury] = r[curx]; curx++; curty = 1; } if (curty != prty) { prty = curty; seg.pb({curx + cury - 1,curx + cury - 1}); } else seg.back().s++; } for (int i = 0; i <= n; i++) dp[i] = inf; // Only consecutive blocks should be connected // [1 1 1] [0 0 ||| 0 0] [1 1 1] // Zeroes that are before "|||" are connected to the left part and ... for (int i = 0; i < (int)seg.size(); i++) { int st = seg[i].f; int nd = seg[i].s; long long val = 0; if (i) { for (int j = seg[i].f; j <= seg[i].s; j++) { int cnt = j - seg[i].f + 1; val += a[j] - a[st]; // If size(seg[i].f --- j) >= size(prev, seg[i - 1].s); int mx = max(st - 1 - cnt + 1, seg[i - 1].f); dp[j] = min(dp[j], sf[mx] + cnt * (a[st] - a[st - 1]) + val); // If size(seg[i].f --- j) < size(prev, seg[i - 1].s); if(st - cnt >= seg[i - 1].f) { dp[j] = min(dp[j], pr[st - cnt] + val); } } for (int j = seg[i].s; j >= seg[i].f - 1; j--) { if (j != -1) dp[j] = min(dp[j], dp[j + 1]); } } if (i == (int)seg.size() - 1) continue; val = 0; for (int j = seg[i].s; j >= seg[i].f; j--) { int cnt = seg[i].s - j + 1; val += a[seg[i].s] - a[j]; sf[j] = val + dp[j - 1]; pr[j] = val + cnt * (a[seg[i + 1].f] - a[nd]) + dp[j - 1]; } for (int j = seg[i].s - 1; j >= seg[i].f; j--) sf[j] = min(sf[j], sf[j + 1]); for (int j = seg[i].f + 1; j <= seg[i].s; j++) pr[j] = min(pr[j], pr[j - 1]); } return dp[n - 1]; } /* int main() { int n, m; assert(2 == scanf("%d %d", &n, &m)); vector<int> r(n), b(m); for(int i = 0; i < n; i++) assert(1 == scanf("%d", &r[i])); for(int i = 0; i < m; i++) assert(1 == scanf("%d", &b[i])); long long res = min_total_length(r, b); printf("%lld\n", res); return 0; }*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...