# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
101902 |
2019-03-21T01:11:55 Z |
briansu |
Wiring (IOI17_wiring) |
C++14 |
|
155 ms |
16116 KB |
#include "wiring.h"
//{
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double lf;
typedef pair<ll,ll> ii;
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define FILL(i,n) memset(i,n,sizeof i)
#define X first
#define Y second
#define SZ(_a) (int)_a.size()
#define ALL(_a) _a.begin(),_a.end()
#define pb push_back
#ifdef brian
#define debug(...) do{\
fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
_do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<" ,";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
_s<<"{";
for(It _it=_ita;_it!=_itb;_it++)
{
_s<<(_it==_ita?"":",")<<*_it;
}
_s<<"}";
return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,multiset<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#endif // brian
//}
const ll MAXn=2e5+5,MAXlg=__lg(MAXn)+2;
const ll MOD=1000000007;
const ll INF=ll(1e15);
ll dp[MAXn];
ll mdp(ll x){return min(dp[x], dp[x-1]);}
long long min_total_length(std::vector<int> r, std::vector<int> b) {
vector<ii> v;
for(ll x:r)v.pb(ii(x, 0));
for(ll x:b)v.pb(ii(x, 1));
sort(ALL(v));
vector<ii> x, y;
int it;
for(it = 0;v[it].Y == v[0].Y;it++)x.pb({v[it].X, it+1});
dp[0] = 0;
REP1(i, SZ(v))dp[i] = INF;
while(it != SZ(v))
{
ll lst = it;
for(;it != SZ(v) && v[it].Y == v[lst].Y;it++)y.pb({v[it].X, it+1});
sort(ALL(x), [](ii a,ii b){return a.X > b.X;});
sort(ALL(y), [](ii a,ii b){return a.X < b.X;});
debug(x, y);
REP1(i, SZ(x) - 1)x[i].X += x[i-1].X;
multiset<ll> st;
for(int i = 0;i < SZ(x);i ++)st.insert(y[0].X * (i + 1) - x[i].X + mdp(x[i].Y));
ll mn = INF, s = 0;
for(int i = 0;i < SZ(y);i ++)
{
if(i < SZ(x))st.erase(st.lower_bound(y[0].X * (i + 1) - x[i].X + mdp(x[i].Y))), mn = min(mn, mdp(x[i].Y) + x[0].X * (i+1) - x[i].X);
debug(i, mn, st);
s += y[i].X;
dp[y[i].Y] = mn + s - (i+1) * x[0].X;
if(SZ(st))dp[y[i].Y] = min(dp[y[i].Y], (*st.begin()) + s - (i+1) * y[0].X);
}
x = y;
y.clear();
}
REP1(i, SZ(v))debug(i, dp[i]);
return dp[SZ(v)];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
3 ms |
384 KB |
Output is correct |
6 |
Correct |
3 ms |
256 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
3 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
3 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
3 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
74 ms |
12384 KB |
Output is correct |
4 |
Correct |
75 ms |
12384 KB |
Output is correct |
5 |
Correct |
64 ms |
11164 KB |
Output is correct |
6 |
Correct |
85 ms |
14564 KB |
Output is correct |
7 |
Correct |
84 ms |
14560 KB |
Output is correct |
8 |
Correct |
89 ms |
14532 KB |
Output is correct |
9 |
Correct |
94 ms |
14608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
92 ms |
6880 KB |
Output is correct |
4 |
Correct |
82 ms |
8288 KB |
Output is correct |
5 |
Correct |
3 ms |
256 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
256 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
3 ms |
384 KB |
Output is correct |
13 |
Correct |
3 ms |
256 KB |
Output is correct |
14 |
Correct |
2 ms |
256 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
256 KB |
Output is correct |
17 |
Correct |
3 ms |
384 KB |
Output is correct |
18 |
Correct |
89 ms |
8672 KB |
Output is correct |
19 |
Correct |
84 ms |
8688 KB |
Output is correct |
20 |
Correct |
74 ms |
8676 KB |
Output is correct |
21 |
Correct |
91 ms |
8688 KB |
Output is correct |
22 |
Correct |
86 ms |
8672 KB |
Output is correct |
23 |
Correct |
81 ms |
8672 KB |
Output is correct |
24 |
Correct |
84 ms |
8672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
88 ms |
7520 KB |
Output is correct |
3 |
Correct |
86 ms |
6880 KB |
Output is correct |
4 |
Correct |
100 ms |
7136 KB |
Output is correct |
5 |
Correct |
65 ms |
6752 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
368 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
3 ms |
384 KB |
Output is correct |
12 |
Correct |
3 ms |
384 KB |
Output is correct |
13 |
Correct |
2 ms |
256 KB |
Output is correct |
14 |
Correct |
2 ms |
256 KB |
Output is correct |
15 |
Correct |
3 ms |
384 KB |
Output is correct |
16 |
Correct |
3 ms |
384 KB |
Output is correct |
17 |
Correct |
2 ms |
384 KB |
Output is correct |
18 |
Correct |
92 ms |
10988 KB |
Output is correct |
19 |
Correct |
106 ms |
8160 KB |
Output is correct |
20 |
Correct |
117 ms |
8088 KB |
Output is correct |
21 |
Correct |
83 ms |
9440 KB |
Output is correct |
22 |
Correct |
99 ms |
14304 KB |
Output is correct |
23 |
Correct |
109 ms |
14404 KB |
Output is correct |
24 |
Correct |
111 ms |
13544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
3 ms |
384 KB |
Output is correct |
6 |
Correct |
3 ms |
256 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
3 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
3 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
3 ms |
384 KB |
Output is correct |
17 |
Correct |
2 ms |
256 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Correct |
74 ms |
12384 KB |
Output is correct |
20 |
Correct |
75 ms |
12384 KB |
Output is correct |
21 |
Correct |
64 ms |
11164 KB |
Output is correct |
22 |
Correct |
85 ms |
14564 KB |
Output is correct |
23 |
Correct |
84 ms |
14560 KB |
Output is correct |
24 |
Correct |
89 ms |
14532 KB |
Output is correct |
25 |
Correct |
94 ms |
14608 KB |
Output is correct |
26 |
Correct |
2 ms |
384 KB |
Output is correct |
27 |
Correct |
2 ms |
384 KB |
Output is correct |
28 |
Correct |
92 ms |
6880 KB |
Output is correct |
29 |
Correct |
82 ms |
8288 KB |
Output is correct |
30 |
Correct |
3 ms |
256 KB |
Output is correct |
31 |
Correct |
2 ms |
256 KB |
Output is correct |
32 |
Correct |
2 ms |
256 KB |
Output is correct |
33 |
Correct |
2 ms |
384 KB |
Output is correct |
34 |
Correct |
3 ms |
384 KB |
Output is correct |
35 |
Correct |
2 ms |
256 KB |
Output is correct |
36 |
Correct |
2 ms |
384 KB |
Output is correct |
37 |
Correct |
3 ms |
384 KB |
Output is correct |
38 |
Correct |
3 ms |
256 KB |
Output is correct |
39 |
Correct |
2 ms |
256 KB |
Output is correct |
40 |
Correct |
2 ms |
384 KB |
Output is correct |
41 |
Correct |
2 ms |
256 KB |
Output is correct |
42 |
Correct |
3 ms |
384 KB |
Output is correct |
43 |
Correct |
89 ms |
8672 KB |
Output is correct |
44 |
Correct |
84 ms |
8688 KB |
Output is correct |
45 |
Correct |
74 ms |
8676 KB |
Output is correct |
46 |
Correct |
91 ms |
8688 KB |
Output is correct |
47 |
Correct |
86 ms |
8672 KB |
Output is correct |
48 |
Correct |
81 ms |
8672 KB |
Output is correct |
49 |
Correct |
84 ms |
8672 KB |
Output is correct |
50 |
Correct |
2 ms |
256 KB |
Output is correct |
51 |
Correct |
88 ms |
7520 KB |
Output is correct |
52 |
Correct |
86 ms |
6880 KB |
Output is correct |
53 |
Correct |
100 ms |
7136 KB |
Output is correct |
54 |
Correct |
65 ms |
6752 KB |
Output is correct |
55 |
Correct |
2 ms |
256 KB |
Output is correct |
56 |
Correct |
2 ms |
384 KB |
Output is correct |
57 |
Correct |
2 ms |
384 KB |
Output is correct |
58 |
Correct |
3 ms |
368 KB |
Output is correct |
59 |
Correct |
2 ms |
384 KB |
Output is correct |
60 |
Correct |
3 ms |
384 KB |
Output is correct |
61 |
Correct |
3 ms |
384 KB |
Output is correct |
62 |
Correct |
2 ms |
256 KB |
Output is correct |
63 |
Correct |
2 ms |
256 KB |
Output is correct |
64 |
Correct |
3 ms |
384 KB |
Output is correct |
65 |
Correct |
3 ms |
384 KB |
Output is correct |
66 |
Correct |
2 ms |
384 KB |
Output is correct |
67 |
Correct |
92 ms |
10988 KB |
Output is correct |
68 |
Correct |
106 ms |
8160 KB |
Output is correct |
69 |
Correct |
117 ms |
8088 KB |
Output is correct |
70 |
Correct |
83 ms |
9440 KB |
Output is correct |
71 |
Correct |
99 ms |
14304 KB |
Output is correct |
72 |
Correct |
109 ms |
14404 KB |
Output is correct |
73 |
Correct |
111 ms |
13544 KB |
Output is correct |
74 |
Correct |
104 ms |
15204 KB |
Output is correct |
75 |
Correct |
116 ms |
12544 KB |
Output is correct |
76 |
Correct |
109 ms |
13420 KB |
Output is correct |
77 |
Correct |
98 ms |
12896 KB |
Output is correct |
78 |
Correct |
109 ms |
13480 KB |
Output is correct |
79 |
Correct |
105 ms |
13000 KB |
Output is correct |
80 |
Correct |
94 ms |
13548 KB |
Output is correct |
81 |
Correct |
111 ms |
15584 KB |
Output is correct |
82 |
Correct |
94 ms |
14948 KB |
Output is correct |
83 |
Correct |
86 ms |
14304 KB |
Output is correct |
84 |
Correct |
89 ms |
15628 KB |
Output is correct |
85 |
Correct |
105 ms |
12256 KB |
Output is correct |
86 |
Correct |
105 ms |
14048 KB |
Output is correct |
87 |
Correct |
102 ms |
14048 KB |
Output is correct |
88 |
Correct |
102 ms |
12896 KB |
Output is correct |
89 |
Correct |
94 ms |
13380 KB |
Output is correct |
90 |
Correct |
109 ms |
13196 KB |
Output is correct |
91 |
Correct |
115 ms |
15040 KB |
Output is correct |
92 |
Correct |
118 ms |
13920 KB |
Output is correct |
93 |
Correct |
115 ms |
14016 KB |
Output is correct |
94 |
Correct |
105 ms |
14692 KB |
Output is correct |
95 |
Correct |
155 ms |
12996 KB |
Output is correct |
96 |
Correct |
104 ms |
14560 KB |
Output is correct |
97 |
Correct |
114 ms |
16116 KB |
Output is correct |
98 |
Correct |
123 ms |
15456 KB |
Output is correct |
99 |
Correct |
119 ms |
15460 KB |
Output is correct |
100 |
Correct |
114 ms |
13892 KB |
Output is correct |
101 |
Correct |
112 ms |
14944 KB |
Output is correct |
102 |
Correct |
110 ms |
13672 KB |
Output is correct |