# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
67471 |
2018-08-14T10:23:36 Z |
zscoder |
Wiring (IOI17_wiring) |
C++17 |
|
127 ms |
104488 KB |
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<ll,ll> ii;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
const int N = 100111;
const int M = 100111;
const int INF = int(1e9)+19;
ll dp[N+M+10];
int lastop[N+M+10]; //last opposite
ll S[N+M+10];
int lastsame[N+M+10];
int nxtsame[N+M+10];
int nxtop[N+M+10];
const int C = N+M;
vi diff[2*(N+M)+15];
int D[N+M+10];
int idxori[N+M+10];
ll sum[2][M+10];
int getid[2][M+10];
ll dpaux[N+M+10];
ll getS(int l, int r)
{
if(l==0) return S[r];
else return S[r]-S[l-1];
}
ll getsum(int id, int l, int r)
{
if(l==0) return sum[id][r];
else return sum[id][r]-sum[id][l-1];
}
long long min_total_length(std::vector<int> r, std::vector<int> b)
{
int n = r.size(); int m = b.size();
r.pb(INF); b.pb(INF);
vector<ii> vec;
vec.pb(mp(-INF,-INF));
int ptrr=0; int ptrb=0;
int di=0;
diff[C].pb(0); D[0]=0;
for(int i=0;i<n+m;i++)
{
if(r[ptrr]<b[ptrb])
{
vec.pb(mp(r[ptrr],0)); idxori[i+1]=ptrr+1; getid[0][ptrr+1]=i+1;
ptrr++; di--;
}
else
{
vec.pb(mp(b[ptrb],1)); idxori[i+1]=ptrb+1; getid[1][ptrb+1]=i+1;
ptrb++; di++;
}
diff[di+C].pb(i+1);
D[i+1]=di;
}
for(int i=1;i<=r.size();i++) sum[0][i]=sum[0][i-1]+r[i-1];
for(int i=1;i<=b.size();i++) sum[1][i]=sum[1][i-1]+b[i-1];
lastop[0]=0;
S[0]=0;
for(int i=1;i<vec.size();i++) S[i]=vec[i].fi+S[i-1];
for(int i=1;i<vec.size();i++) lastop[i]=(vec[i-1].se==vec[i].se?lastop[i-1]:i-1);
for(int i=1;i<vec.size();i++) lastsame[i]=(vec[i-1].se==vec[i].se?i-1:lastop[i-1]);
nxtop[int(vec.size())-1]=INF; nxtsame[int(vec.size())-1]=INF;
for(int i=int(vec.size())-2;i>=0;i--) nxtop[i]=(vec[i].se==vec[i+1].se?nxtop[i+1]:i+1);
for(int i=int(vec.size())-2;i>=0;i--) nxtsame[i]=(vec[i].se==vec[i+1].se?i+1:nxtop[i+1]);
for(int i=0;i<N+M+10;i++){dp[i]=ll(1e18);}
dp[0]=0;
for(int i=1;i<=n+m;i++)
{
ll pos=vec[i].fi; int ty=vec[i].se;
//spam opposite sides;
{
if(lastop[i]>0) dp[i] = min(dp[i], dp[i-1]+pos-vec[lastop[i]].fi);
ll d=0;
for(int k=i-1;vec[k].se==(ty^1);k--)
{
d+=pos-vec[k].fi;
dp[i] = min(dp[i], dp[k-1] + d);
}
int ID=lower_bound(diff[D[i]+C].begin(),diff[D[i]+C].end(),i)-diff[D[i]+C].begin();
ID--;
if(ID>=0)
{
int siz = i-diff[D[i]+C][ID]; siz>>=1;
d=getsum(ty,idxori[i]-siz+1,idxori[i])-getsum(ty^1,idxori[lastop[i]]-siz+1,idxori[lastop[i]]);
int curb=lastsame[diff[D[i]+C][ID]+1];
int curr=getid[ty][idxori[i]-siz];
dp[i] = min(dp[i], dp[max(curr,curb)] + d); int nxtr=getid[ty][idxori[i]-siz+1];
if(curb>0&&vec[curb].fi>vec[curr].fi) dp[i] = min(dp[i], dpaux[curb]+d);
}
}
{
dpaux[i]=ll(1e18);
if(nxtop[i]<=n+m) dpaux[i]=vec[nxtop[i]].fi-vec[i].fi+dp[i-1];
if(vec[i].se==vec[i-1].se&&nxtop[i]<=n+m) dpaux[i]=min(dpaux[i],dpaux[i-1]+vec[nxtop[i]].fi-vec[i].fi);
}
}
return dp[n+m];
}
Compilation message
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:68:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<=r.size();i++) sum[0][i]=sum[0][i-1]+r[i-1];
~^~~~~~~~~~
wiring.cpp:69:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<=b.size();i++) sum[1][i]=sum[1][i-1]+b[i-1];
~^~~~~~~~~~
wiring.cpp:72:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<vec.size();i++) S[i]=vec[i].fi+S[i-1];
~^~~~~~~~~~~
wiring.cpp:73:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<vec.size();i++) lastop[i]=(vec[i-1].se==vec[i].se?lastop[i-1]:i-1);
~^~~~~~~~~~~
wiring.cpp:74:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<vec.size();i++) lastsame[i]=(vec[i-1].se==vec[i].se?i-1:lastop[i-1]);
~^~~~~~~~~~~
wiring.cpp:100:53: warning: unused variable 'nxtr' [-Wunused-variable]
dp[i] = min(dp[i], dp[max(curr,curb)] + d); int nxtr=getid[ty][idxori[i]-siz+1];
^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
11256 KB |
Output is correct |
2 |
Correct |
13 ms |
11364 KB |
Output is correct |
3 |
Correct |
13 ms |
11528 KB |
Output is correct |
4 |
Correct |
12 ms |
11528 KB |
Output is correct |
5 |
Correct |
12 ms |
11588 KB |
Output is correct |
6 |
Correct |
12 ms |
11592 KB |
Output is correct |
7 |
Correct |
14 ms |
11656 KB |
Output is correct |
8 |
Correct |
13 ms |
11656 KB |
Output is correct |
9 |
Correct |
14 ms |
11656 KB |
Output is correct |
10 |
Correct |
12 ms |
11656 KB |
Output is correct |
11 |
Correct |
13 ms |
11656 KB |
Output is correct |
12 |
Correct |
14 ms |
11656 KB |
Output is correct |
13 |
Correct |
14 ms |
11656 KB |
Output is correct |
14 |
Correct |
12 ms |
11656 KB |
Output is correct |
15 |
Correct |
11 ms |
11656 KB |
Output is correct |
16 |
Correct |
12 ms |
11656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
11656 KB |
Output is correct |
2 |
Correct |
14 ms |
11656 KB |
Output is correct |
3 |
Correct |
67 ms |
25888 KB |
Output is correct |
4 |
Correct |
64 ms |
27424 KB |
Output is correct |
5 |
Correct |
72 ms |
28800 KB |
Output is correct |
6 |
Correct |
127 ms |
34532 KB |
Output is correct |
7 |
Correct |
89 ms |
36452 KB |
Output is correct |
8 |
Correct |
102 ms |
38336 KB |
Output is correct |
9 |
Correct |
87 ms |
40268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
40268 KB |
Output is correct |
2 |
Correct |
11 ms |
40268 KB |
Output is correct |
3 |
Correct |
91 ms |
40268 KB |
Output is correct |
4 |
Correct |
78 ms |
40268 KB |
Output is correct |
5 |
Correct |
12 ms |
40268 KB |
Output is correct |
6 |
Correct |
14 ms |
40268 KB |
Output is correct |
7 |
Correct |
13 ms |
40268 KB |
Output is correct |
8 |
Correct |
12 ms |
40268 KB |
Output is correct |
9 |
Correct |
12 ms |
40268 KB |
Output is correct |
10 |
Correct |
13 ms |
40268 KB |
Output is correct |
11 |
Correct |
15 ms |
40268 KB |
Output is correct |
12 |
Correct |
12 ms |
40268 KB |
Output is correct |
13 |
Correct |
13 ms |
40268 KB |
Output is correct |
14 |
Correct |
12 ms |
40268 KB |
Output is correct |
15 |
Correct |
12 ms |
40268 KB |
Output is correct |
16 |
Correct |
13 ms |
40268 KB |
Output is correct |
17 |
Correct |
12 ms |
40268 KB |
Output is correct |
18 |
Correct |
85 ms |
40268 KB |
Output is correct |
19 |
Correct |
91 ms |
40268 KB |
Output is correct |
20 |
Correct |
111 ms |
40268 KB |
Output is correct |
21 |
Correct |
95 ms |
40268 KB |
Output is correct |
22 |
Correct |
85 ms |
40268 KB |
Output is correct |
23 |
Correct |
84 ms |
40268 KB |
Output is correct |
24 |
Correct |
89 ms |
40268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
40268 KB |
Output is correct |
2 |
Correct |
102 ms |
40268 KB |
Output is correct |
3 |
Correct |
80 ms |
40268 KB |
Output is correct |
4 |
Correct |
75 ms |
41044 KB |
Output is correct |
5 |
Correct |
82 ms |
42188 KB |
Output is correct |
6 |
Correct |
13 ms |
42188 KB |
Output is correct |
7 |
Correct |
12 ms |
42188 KB |
Output is correct |
8 |
Correct |
13 ms |
42188 KB |
Output is correct |
9 |
Correct |
13 ms |
42188 KB |
Output is correct |
10 |
Correct |
14 ms |
42188 KB |
Output is correct |
11 |
Correct |
13 ms |
42188 KB |
Output is correct |
12 |
Correct |
14 ms |
42188 KB |
Output is correct |
13 |
Correct |
12 ms |
42188 KB |
Output is correct |
14 |
Correct |
13 ms |
42188 KB |
Output is correct |
15 |
Correct |
13 ms |
42188 KB |
Output is correct |
16 |
Correct |
11 ms |
42188 KB |
Output is correct |
17 |
Correct |
13 ms |
42188 KB |
Output is correct |
18 |
Correct |
111 ms |
43916 KB |
Output is correct |
19 |
Correct |
89 ms |
45012 KB |
Output is correct |
20 |
Correct |
70 ms |
46052 KB |
Output is correct |
21 |
Correct |
77 ms |
47628 KB |
Output is correct |
22 |
Correct |
74 ms |
50224 KB |
Output is correct |
23 |
Correct |
76 ms |
51368 KB |
Output is correct |
24 |
Correct |
75 ms |
52120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
11256 KB |
Output is correct |
2 |
Correct |
13 ms |
11364 KB |
Output is correct |
3 |
Correct |
13 ms |
11528 KB |
Output is correct |
4 |
Correct |
12 ms |
11528 KB |
Output is correct |
5 |
Correct |
12 ms |
11588 KB |
Output is correct |
6 |
Correct |
12 ms |
11592 KB |
Output is correct |
7 |
Correct |
14 ms |
11656 KB |
Output is correct |
8 |
Correct |
13 ms |
11656 KB |
Output is correct |
9 |
Correct |
14 ms |
11656 KB |
Output is correct |
10 |
Correct |
12 ms |
11656 KB |
Output is correct |
11 |
Correct |
13 ms |
11656 KB |
Output is correct |
12 |
Correct |
14 ms |
11656 KB |
Output is correct |
13 |
Correct |
14 ms |
11656 KB |
Output is correct |
14 |
Correct |
12 ms |
11656 KB |
Output is correct |
15 |
Correct |
11 ms |
11656 KB |
Output is correct |
16 |
Correct |
12 ms |
11656 KB |
Output is correct |
17 |
Correct |
11 ms |
11656 KB |
Output is correct |
18 |
Correct |
14 ms |
11656 KB |
Output is correct |
19 |
Correct |
67 ms |
25888 KB |
Output is correct |
20 |
Correct |
64 ms |
27424 KB |
Output is correct |
21 |
Correct |
72 ms |
28800 KB |
Output is correct |
22 |
Correct |
127 ms |
34532 KB |
Output is correct |
23 |
Correct |
89 ms |
36452 KB |
Output is correct |
24 |
Correct |
102 ms |
38336 KB |
Output is correct |
25 |
Correct |
87 ms |
40268 KB |
Output is correct |
26 |
Correct |
11 ms |
40268 KB |
Output is correct |
27 |
Correct |
11 ms |
40268 KB |
Output is correct |
28 |
Correct |
91 ms |
40268 KB |
Output is correct |
29 |
Correct |
78 ms |
40268 KB |
Output is correct |
30 |
Correct |
12 ms |
40268 KB |
Output is correct |
31 |
Correct |
14 ms |
40268 KB |
Output is correct |
32 |
Correct |
13 ms |
40268 KB |
Output is correct |
33 |
Correct |
12 ms |
40268 KB |
Output is correct |
34 |
Correct |
12 ms |
40268 KB |
Output is correct |
35 |
Correct |
13 ms |
40268 KB |
Output is correct |
36 |
Correct |
15 ms |
40268 KB |
Output is correct |
37 |
Correct |
12 ms |
40268 KB |
Output is correct |
38 |
Correct |
13 ms |
40268 KB |
Output is correct |
39 |
Correct |
12 ms |
40268 KB |
Output is correct |
40 |
Correct |
12 ms |
40268 KB |
Output is correct |
41 |
Correct |
13 ms |
40268 KB |
Output is correct |
42 |
Correct |
12 ms |
40268 KB |
Output is correct |
43 |
Correct |
85 ms |
40268 KB |
Output is correct |
44 |
Correct |
91 ms |
40268 KB |
Output is correct |
45 |
Correct |
111 ms |
40268 KB |
Output is correct |
46 |
Correct |
95 ms |
40268 KB |
Output is correct |
47 |
Correct |
85 ms |
40268 KB |
Output is correct |
48 |
Correct |
84 ms |
40268 KB |
Output is correct |
49 |
Correct |
89 ms |
40268 KB |
Output is correct |
50 |
Correct |
13 ms |
40268 KB |
Output is correct |
51 |
Correct |
102 ms |
40268 KB |
Output is correct |
52 |
Correct |
80 ms |
40268 KB |
Output is correct |
53 |
Correct |
75 ms |
41044 KB |
Output is correct |
54 |
Correct |
82 ms |
42188 KB |
Output is correct |
55 |
Correct |
13 ms |
42188 KB |
Output is correct |
56 |
Correct |
12 ms |
42188 KB |
Output is correct |
57 |
Correct |
13 ms |
42188 KB |
Output is correct |
58 |
Correct |
13 ms |
42188 KB |
Output is correct |
59 |
Correct |
14 ms |
42188 KB |
Output is correct |
60 |
Correct |
13 ms |
42188 KB |
Output is correct |
61 |
Correct |
14 ms |
42188 KB |
Output is correct |
62 |
Correct |
12 ms |
42188 KB |
Output is correct |
63 |
Correct |
13 ms |
42188 KB |
Output is correct |
64 |
Correct |
13 ms |
42188 KB |
Output is correct |
65 |
Correct |
11 ms |
42188 KB |
Output is correct |
66 |
Correct |
13 ms |
42188 KB |
Output is correct |
67 |
Correct |
111 ms |
43916 KB |
Output is correct |
68 |
Correct |
89 ms |
45012 KB |
Output is correct |
69 |
Correct |
70 ms |
46052 KB |
Output is correct |
70 |
Correct |
77 ms |
47628 KB |
Output is correct |
71 |
Correct |
74 ms |
50224 KB |
Output is correct |
72 |
Correct |
76 ms |
51368 KB |
Output is correct |
73 |
Correct |
75 ms |
52120 KB |
Output is correct |
74 |
Correct |
84 ms |
54620 KB |
Output is correct |
75 |
Correct |
79 ms |
55968 KB |
Output is correct |
76 |
Correct |
88 ms |
57544 KB |
Output is correct |
77 |
Correct |
68 ms |
58996 KB |
Output is correct |
78 |
Correct |
68 ms |
60372 KB |
Output is correct |
79 |
Correct |
73 ms |
61892 KB |
Output is correct |
80 |
Correct |
75 ms |
63196 KB |
Output is correct |
81 |
Correct |
79 ms |
65072 KB |
Output is correct |
82 |
Correct |
76 ms |
66636 KB |
Output is correct |
83 |
Correct |
71 ms |
67780 KB |
Output is correct |
84 |
Correct |
78 ms |
70124 KB |
Output is correct |
85 |
Correct |
86 ms |
71544 KB |
Output is correct |
86 |
Correct |
88 ms |
73232 KB |
Output is correct |
87 |
Correct |
115 ms |
75296 KB |
Output is correct |
88 |
Correct |
84 ms |
77076 KB |
Output is correct |
89 |
Correct |
96 ms |
79060 KB |
Output is correct |
90 |
Correct |
85 ms |
80628 KB |
Output is correct |
91 |
Correct |
87 ms |
83452 KB |
Output is correct |
92 |
Correct |
83 ms |
85000 KB |
Output is correct |
93 |
Correct |
94 ms |
87192 KB |
Output is correct |
94 |
Correct |
88 ms |
89112 KB |
Output is correct |
95 |
Correct |
89 ms |
90680 KB |
Output is correct |
96 |
Correct |
76 ms |
92948 KB |
Output is correct |
97 |
Correct |
82 ms |
95452 KB |
Output is correct |
98 |
Correct |
81 ms |
97124 KB |
Output is correct |
99 |
Correct |
76 ms |
99072 KB |
Output is correct |
100 |
Correct |
87 ms |
100684 KB |
Output is correct |
101 |
Correct |
84 ms |
102876 KB |
Output is correct |
102 |
Correct |
83 ms |
104488 KB |
Output is correct |