# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
65998 |
2018-08-09T10:00:03 Z |
FedericoS |
Wiring (IOI17_wiring) |
C++14 |
|
325 ms |
90512 KB |
#include <iostream>
#include <algorithm>
#include "wiring.h"
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;
ll INF=1e18;
int N,M,K;
ll A[100005],B[100005];
vector<pll> W;
vector<ll> DP[100005],V[100005],R[2][100005];
ll D,res,ans;
void insert(int k, int l, int r, int t, int g, int j, ll a){
if(j<l or j>r)return;
if(l==r)R[t][g][k]=a;
else{
int m=(l+r)/2;
insert(2*k,l,m,t,g,j,a);
insert(2*k+1,m+1,r,t,g,j,a);
R[t][g][k]=min(R[t][g][2*k],R[t][g][2*k+1]);
}
}
void inserisci(int g, int j, ll a){
//cout<<"inserisci "<<g<<" "<<j<<" "<<a<<endl;
insert(1,0,DP[g].size(),0,g,j,a);
insert(1,0,DP[g].size(),1,g,j,a-((ll)DP[g].size()-j-1)*(V[g+1][0]-V[g][DP[g].size()-2]));
/*
R[0][g][j]=a;
R[1][g][j]=a-((ll)DP[g].size()-j-1)*(V[g+1][0]-V[g][DP[g].size()-2]);
*/
}
ll query(int k, int l, int r, int t, int g, int a, int b){
if(b<l or r<a)return INF;
if(a<=l and r<=b)return R[t][g][k];
int m=(l+r)/2;
return min(query(2*k,l,m,t,g,a,b),query(2*k+1,m+1,r,t,g,a,b));
}
ll minimo(int t, int g, int a, int b){
/*
ll res2=INF;
for(int i=a;i<b;i++)
res2=min(res2,R[t][g][i]);
*/
ll res=INF;
if(b<=a)
res=INF;
else
res=query(1,0,DP[g].size(),t,g,a,b-1);
//cout<<"minimo "<<t<<" "<<g<<" "<<a<<" "<<b<<" "<<res<<" "<<res2<<endl;
return res;
}
void stampa(){
for(int i=0;i<K;i++){
cout<<"gruppo "<<i<<endl;
for(ll g:DP[i])
cout<<g<<" ";
cout<<endl;
}
}
long long min_total_length(std::vector<int> r, std::vector<int> b) {
N=r.size();
M=b.size();
for(int a:r)
W.push_back({a,0});
for(int a:b)
W.push_back({a,1});
sort(W.begin(),W.end());
V[0].push_back(W[0].first);
DP[0].push_back(INF);
for(int i=1;i<N+M;i++){
if(W[i].second!=W[i-1].second)
K++;
V[K].push_back(W[i].first);
DP[K].push_back(INF);
}
K++;
for(int i=0;i<K;i++)
DP[i].push_back(INF);
for(int i=0;i<K;i++){
R[0][i].resize(4*DP[i].size(),INF);
R[1][i].resize(4*DP[i].size(),INF);
}
D=0;
for(int i:V[0])
D+=V[1][0]-i;
DP[0][0]=D;
inserisci(0,0,D);
for(int g=1;g<K-1;g++){
D=0;
for(int i:V[g])
D+=V[g+1][0]-i;
for(ll i=0;i<DP[g].size();i++){
res=INF;
res=min(res,minimo(0,g-1,0,(ll)DP[g-1].size()-i)+D);
res=min(res,minimo(1,g-1,max((ll)DP[g-1].size()-i,0LL),(ll)DP[g-1].size())+D+(V[g][0]-V[g-1][DP[g-1].size()-2])*i);
/*
for(int j=0;j<(int)DP[g-1].size()-i;j++)
res=min(res,DP[g-1][j]+D);
for(int j=max((int)DP[g-1].size()-i,0);j<DP[g-1].size();j++)
res=min(res,DP[g-1][j]+D+(i-(ll)DP[g-1].size()+j+1)*(V[g][0]-V[g-1][DP[g-1].size()-2]));
*/
DP[g][i]=res;
inserisci(g,i,res);
if(i!=V[g].size()){
D-=V[g+1][0]-V[g][i];
D+=V[g][i]-V[g][0];
}
}
}
D=0;
for(int i:V[K-1])
D+=i-V[K-1][0];
ans=INF;
int g=K-1;
int i=(int)DP[g].size()-1;
for(int j=0;j<(int)DP[g-1].size()-i;j++)
ans=min(ans,DP[g-1][j]+D);
for(int j=max((int)DP[g-1].size()-i,0);j<DP[g-1].size();j++)
ans=min(ans,DP[g-1][j]+D+(i-(ll)DP[g-1].size()+j+1)*(V[g][0]-V[g-1][DP[g-1].size()-2]));
//stampa();
return ans;
}
/*
4 5
1 2 3 7
0 4 5 9 10
*/
/*
for(int i=0;i<K;i++){
cout<<"i "<<i<<endl;
for(int g:V[i])
cout<<g<<" ";
cout<<endl;
}
*/
Compilation message
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:124:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll i=0;i<DP[g].size();i++){
~^~~~~~~~~~~~~
wiring.cpp:139:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i!=V[g].size()){
~^~~~~~~~~~~~~
wiring.cpp:157:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=max((int)DP[g-1].size()-i,0);j<DP[g-1].size();j++)
~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
9720 KB |
Output is correct |
2 |
Correct |
12 ms |
9720 KB |
Output is correct |
3 |
Correct |
12 ms |
9888 KB |
Output is correct |
4 |
Correct |
12 ms |
9888 KB |
Output is correct |
5 |
Correct |
11 ms |
9888 KB |
Output is correct |
6 |
Correct |
12 ms |
9888 KB |
Output is correct |
7 |
Correct |
12 ms |
9892 KB |
Output is correct |
8 |
Correct |
12 ms |
9892 KB |
Output is correct |
9 |
Correct |
13 ms |
9896 KB |
Output is correct |
10 |
Correct |
13 ms |
9932 KB |
Output is correct |
11 |
Correct |
12 ms |
9932 KB |
Output is correct |
12 |
Correct |
12 ms |
9932 KB |
Output is correct |
13 |
Correct |
11 ms |
10020 KB |
Output is correct |
14 |
Correct |
12 ms |
10020 KB |
Output is correct |
15 |
Correct |
13 ms |
10020 KB |
Output is correct |
16 |
Correct |
12 ms |
10020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
10020 KB |
Output is correct |
2 |
Correct |
12 ms |
10020 KB |
Output is correct |
3 |
Correct |
85 ms |
25808 KB |
Output is correct |
4 |
Correct |
83 ms |
25912 KB |
Output is correct |
5 |
Correct |
66 ms |
26424 KB |
Output is correct |
6 |
Correct |
80 ms |
31720 KB |
Output is correct |
7 |
Correct |
84 ms |
31744 KB |
Output is correct |
8 |
Correct |
72 ms |
31744 KB |
Output is correct |
9 |
Correct |
79 ms |
31820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
31820 KB |
Output is correct |
2 |
Correct |
12 ms |
31820 KB |
Output is correct |
3 |
Correct |
179 ms |
39188 KB |
Output is correct |
4 |
Correct |
178 ms |
39188 KB |
Output is correct |
5 |
Correct |
10 ms |
39188 KB |
Output is correct |
6 |
Correct |
10 ms |
39188 KB |
Output is correct |
7 |
Correct |
11 ms |
39188 KB |
Output is correct |
8 |
Correct |
11 ms |
39188 KB |
Output is correct |
9 |
Correct |
11 ms |
39188 KB |
Output is correct |
10 |
Correct |
11 ms |
39188 KB |
Output is correct |
11 |
Correct |
10 ms |
39188 KB |
Output is correct |
12 |
Correct |
12 ms |
39188 KB |
Output is correct |
13 |
Correct |
10 ms |
39188 KB |
Output is correct |
14 |
Correct |
12 ms |
39188 KB |
Output is correct |
15 |
Correct |
12 ms |
39188 KB |
Output is correct |
16 |
Correct |
11 ms |
39188 KB |
Output is correct |
17 |
Correct |
11 ms |
39188 KB |
Output is correct |
18 |
Correct |
185 ms |
39268 KB |
Output is correct |
19 |
Correct |
191 ms |
39268 KB |
Output is correct |
20 |
Correct |
168 ms |
39268 KB |
Output is correct |
21 |
Correct |
201 ms |
39268 KB |
Output is correct |
22 |
Correct |
166 ms |
39268 KB |
Output is correct |
23 |
Correct |
172 ms |
39268 KB |
Output is correct |
24 |
Correct |
173 ms |
39268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
39268 KB |
Output is correct |
2 |
Correct |
311 ms |
39268 KB |
Output is correct |
3 |
Correct |
198 ms |
39268 KB |
Output is correct |
4 |
Correct |
296 ms |
39268 KB |
Output is correct |
5 |
Correct |
162 ms |
39268 KB |
Output is correct |
6 |
Correct |
11 ms |
39268 KB |
Output is correct |
7 |
Correct |
11 ms |
39268 KB |
Output is correct |
8 |
Correct |
11 ms |
39268 KB |
Output is correct |
9 |
Correct |
13 ms |
39268 KB |
Output is correct |
10 |
Correct |
12 ms |
39268 KB |
Output is correct |
11 |
Correct |
12 ms |
39268 KB |
Output is correct |
12 |
Correct |
12 ms |
39268 KB |
Output is correct |
13 |
Correct |
10 ms |
39268 KB |
Output is correct |
14 |
Correct |
11 ms |
39268 KB |
Output is correct |
15 |
Correct |
13 ms |
39268 KB |
Output is correct |
16 |
Correct |
13 ms |
39268 KB |
Output is correct |
17 |
Correct |
11 ms |
39268 KB |
Output is correct |
18 |
Correct |
228 ms |
39268 KB |
Output is correct |
19 |
Correct |
221 ms |
39268 KB |
Output is correct |
20 |
Correct |
296 ms |
39268 KB |
Output is correct |
21 |
Correct |
252 ms |
39268 KB |
Output is correct |
22 |
Correct |
214 ms |
39268 KB |
Output is correct |
23 |
Correct |
166 ms |
39268 KB |
Output is correct |
24 |
Correct |
215 ms |
39268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
9720 KB |
Output is correct |
2 |
Correct |
12 ms |
9720 KB |
Output is correct |
3 |
Correct |
12 ms |
9888 KB |
Output is correct |
4 |
Correct |
12 ms |
9888 KB |
Output is correct |
5 |
Correct |
11 ms |
9888 KB |
Output is correct |
6 |
Correct |
12 ms |
9888 KB |
Output is correct |
7 |
Correct |
12 ms |
9892 KB |
Output is correct |
8 |
Correct |
12 ms |
9892 KB |
Output is correct |
9 |
Correct |
13 ms |
9896 KB |
Output is correct |
10 |
Correct |
13 ms |
9932 KB |
Output is correct |
11 |
Correct |
12 ms |
9932 KB |
Output is correct |
12 |
Correct |
12 ms |
9932 KB |
Output is correct |
13 |
Correct |
11 ms |
10020 KB |
Output is correct |
14 |
Correct |
12 ms |
10020 KB |
Output is correct |
15 |
Correct |
13 ms |
10020 KB |
Output is correct |
16 |
Correct |
12 ms |
10020 KB |
Output is correct |
17 |
Correct |
11 ms |
10020 KB |
Output is correct |
18 |
Correct |
12 ms |
10020 KB |
Output is correct |
19 |
Correct |
85 ms |
25808 KB |
Output is correct |
20 |
Correct |
83 ms |
25912 KB |
Output is correct |
21 |
Correct |
66 ms |
26424 KB |
Output is correct |
22 |
Correct |
80 ms |
31720 KB |
Output is correct |
23 |
Correct |
84 ms |
31744 KB |
Output is correct |
24 |
Correct |
72 ms |
31744 KB |
Output is correct |
25 |
Correct |
79 ms |
31820 KB |
Output is correct |
26 |
Correct |
11 ms |
31820 KB |
Output is correct |
27 |
Correct |
12 ms |
31820 KB |
Output is correct |
28 |
Correct |
179 ms |
39188 KB |
Output is correct |
29 |
Correct |
178 ms |
39188 KB |
Output is correct |
30 |
Correct |
10 ms |
39188 KB |
Output is correct |
31 |
Correct |
10 ms |
39188 KB |
Output is correct |
32 |
Correct |
11 ms |
39188 KB |
Output is correct |
33 |
Correct |
11 ms |
39188 KB |
Output is correct |
34 |
Correct |
11 ms |
39188 KB |
Output is correct |
35 |
Correct |
11 ms |
39188 KB |
Output is correct |
36 |
Correct |
10 ms |
39188 KB |
Output is correct |
37 |
Correct |
12 ms |
39188 KB |
Output is correct |
38 |
Correct |
10 ms |
39188 KB |
Output is correct |
39 |
Correct |
12 ms |
39188 KB |
Output is correct |
40 |
Correct |
12 ms |
39188 KB |
Output is correct |
41 |
Correct |
11 ms |
39188 KB |
Output is correct |
42 |
Correct |
11 ms |
39188 KB |
Output is correct |
43 |
Correct |
185 ms |
39268 KB |
Output is correct |
44 |
Correct |
191 ms |
39268 KB |
Output is correct |
45 |
Correct |
168 ms |
39268 KB |
Output is correct |
46 |
Correct |
201 ms |
39268 KB |
Output is correct |
47 |
Correct |
166 ms |
39268 KB |
Output is correct |
48 |
Correct |
172 ms |
39268 KB |
Output is correct |
49 |
Correct |
173 ms |
39268 KB |
Output is correct |
50 |
Correct |
11 ms |
39268 KB |
Output is correct |
51 |
Correct |
311 ms |
39268 KB |
Output is correct |
52 |
Correct |
198 ms |
39268 KB |
Output is correct |
53 |
Correct |
296 ms |
39268 KB |
Output is correct |
54 |
Correct |
162 ms |
39268 KB |
Output is correct |
55 |
Correct |
11 ms |
39268 KB |
Output is correct |
56 |
Correct |
11 ms |
39268 KB |
Output is correct |
57 |
Correct |
11 ms |
39268 KB |
Output is correct |
58 |
Correct |
13 ms |
39268 KB |
Output is correct |
59 |
Correct |
12 ms |
39268 KB |
Output is correct |
60 |
Correct |
12 ms |
39268 KB |
Output is correct |
61 |
Correct |
12 ms |
39268 KB |
Output is correct |
62 |
Correct |
10 ms |
39268 KB |
Output is correct |
63 |
Correct |
11 ms |
39268 KB |
Output is correct |
64 |
Correct |
13 ms |
39268 KB |
Output is correct |
65 |
Correct |
13 ms |
39268 KB |
Output is correct |
66 |
Correct |
11 ms |
39268 KB |
Output is correct |
67 |
Correct |
228 ms |
39268 KB |
Output is correct |
68 |
Correct |
221 ms |
39268 KB |
Output is correct |
69 |
Correct |
296 ms |
39268 KB |
Output is correct |
70 |
Correct |
252 ms |
39268 KB |
Output is correct |
71 |
Correct |
214 ms |
39268 KB |
Output is correct |
72 |
Correct |
166 ms |
39268 KB |
Output is correct |
73 |
Correct |
215 ms |
39268 KB |
Output is correct |
74 |
Correct |
246 ms |
40268 KB |
Output is correct |
75 |
Correct |
272 ms |
42044 KB |
Output is correct |
76 |
Correct |
220 ms |
44048 KB |
Output is correct |
77 |
Correct |
325 ms |
45372 KB |
Output is correct |
78 |
Correct |
308 ms |
47008 KB |
Output is correct |
79 |
Correct |
226 ms |
48132 KB |
Output is correct |
80 |
Correct |
236 ms |
49480 KB |
Output is correct |
81 |
Correct |
196 ms |
51028 KB |
Output is correct |
82 |
Correct |
208 ms |
52076 KB |
Output is correct |
83 |
Correct |
143 ms |
54644 KB |
Output is correct |
84 |
Correct |
128 ms |
56040 KB |
Output is correct |
85 |
Correct |
227 ms |
57584 KB |
Output is correct |
86 |
Correct |
188 ms |
60092 KB |
Output is correct |
87 |
Correct |
167 ms |
62236 KB |
Output is correct |
88 |
Correct |
205 ms |
63764 KB |
Output is correct |
89 |
Correct |
224 ms |
65380 KB |
Output is correct |
90 |
Correct |
251 ms |
67836 KB |
Output is correct |
91 |
Correct |
196 ms |
69212 KB |
Output is correct |
92 |
Correct |
219 ms |
71400 KB |
Output is correct |
93 |
Correct |
200 ms |
73092 KB |
Output is correct |
94 |
Correct |
230 ms |
75024 KB |
Output is correct |
95 |
Correct |
262 ms |
76700 KB |
Output is correct |
96 |
Correct |
210 ms |
79400 KB |
Output is correct |
97 |
Correct |
226 ms |
80636 KB |
Output is correct |
98 |
Correct |
239 ms |
83152 KB |
Output is correct |
99 |
Correct |
315 ms |
84956 KB |
Output is correct |
100 |
Correct |
287 ms |
86712 KB |
Output is correct |
101 |
Correct |
225 ms |
88520 KB |
Output is correct |
102 |
Correct |
200 ms |
90512 KB |
Output is correct |