# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
883871 | 2023-12-06T10:08:01 Z | JakobZorz | Wiring (IOI17_wiring) | C++14 | 1000 ms | 8976 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()) 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; } 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 | Incorrect | 0 ms | 348 KB | 3rd lines differ - on the 1st token, expected: '14340', found: '14694' |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Execution timed out | 1052 ms | 6600 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Incorrect | 36 ms | 8712 KB | 3rd lines differ - on the 1st token, expected: '1068938599', found: '1152497305' |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Execution timed out | 1024 ms | 8976 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 | Incorrect | 0 ms | 348 KB | 3rd lines differ - on the 1st token, expected: '14340', found: '14694' |
3 | Halted | 0 ms | 0 KB | - |