# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
883905 | 2023-12-06T11:19:21 Z | JakobZorz | Wiring (IOI17_wiring) | C++14 | 1000 ms | 10340 KB |
#include"wiring.h" #include<iostream> #include<algorithm> using namespace std; typedef long long ll; ll min_total_length(vector<int>r,vector<int>b){ vector<pair<int,int>>arr; for(int i:r) arr.push_back({i,0}); for(int i:b) arr.push_back({i,1}); sort(arr.begin(),arr.end()); vector<ll>dp(arr.size(),1e18); dp.push_back(0); arr.emplace_back(-1,arr.back().second^1); int i2=(int)dp.size()-1; int i3=(int)dp.size()-1; for(int i1=(int)dp.size()-2;i1>=0;i1--){ if(arr[i2].second==arr[i1].second){ i3=i2; i2=i1+1; } if(i2==dp.size()-1) continue; int mid=arr[i2].first; //cout<<"mid "<<mid<<"\n"; ll cost=0; int num1=i2-i1; int first1=arr[i2-1].first; //cout<<"first1 "<<first1<<"\n"; for(int i=i1;i<i2;i++){ //cout<<"i "<<mid<<" - "<<arr[i].first<<"\n"; cost+=mid-arr[i].first; } dp[i1]=cost+dp[i2]; for(int i=i2;i<i3;i++){ if(num1==0){ cost+=arr[i].first-first1; }else{ num1--; cost+=arr[i].first-mid; } //cout<<"i "<<dp.size()<<" "<<i+1<<"\n"; dp[i1]=min(dp[i1],dp[i+1]+cost); } //cout<<"dp["<<i1<<"] = "<<dp[i1]<<"\n"; } return dp[0]; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 1 ms | 432 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 0 ms | 344 KB | Output is correct |
11 | Correct | 1 ms | 344 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 0 ms | 348 KB | Output is correct |
14 | Correct | 0 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 600 KB | Output is correct |
3 | Execution timed out | 1092 ms | 6264 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 504 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 34 ms | 6780 KB | Output is correct |
4 | Correct | 41 ms | 8364 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 1 ms | 344 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 0 ms | 348 KB | Output is correct |
14 | Correct | 0 ms | 348 KB | Output is correct |
15 | Correct | 1 ms | 348 KB | Output is correct |
16 | Correct | 0 ms | 356 KB | Output is correct |
17 | Correct | 0 ms | 348 KB | Output is correct |
18 | Correct | 35 ms | 9412 KB | Output is correct |
19 | Correct | 35 ms | 8528 KB | Output is correct |
20 | Correct | 38 ms | 8716 KB | Output is correct |
21 | Correct | 34 ms | 8652 KB | Output is correct |
22 | Correct | 35 ms | 8752 KB | Output is correct |
23 | Correct | 41 ms | 10340 KB | Output is correct |
24 | Correct | 35 ms | 8644 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
2 | Execution timed out | 1073 ms | 6780 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 1 ms | 432 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 0 ms | 344 KB | Output is correct |
11 | Correct | 1 ms | 344 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 0 ms | 348 KB | Output is correct |
14 | Correct | 0 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 0 ms | 348 KB | Output is correct |
17 | Correct | 0 ms | 348 KB | Output is correct |
18 | Correct | 0 ms | 600 KB | Output is correct |
19 | Execution timed out | 1092 ms | 6264 KB | Time limit exceeded |
20 | Halted | 0 ms | 0 KB | - |