# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
883908 | 2023-12-06T11:23:56 Z | JakobZorz | 전선 연결 (IOI17_wiring) | C++14 | 1000 ms | 8048 KB |
#include"wiring.h" #include<iostream> #include<algorithm> #include<set> 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; multiset<int>ms; ll cost1=0; for(int i1=(int)dp.size()-2;i1>=0;i1--){ if(arr[i2].second==arr[i1].second){ i3=i2; i2=i1+1; cost1=0; } if(i2==dp.size()-1) continue; int mid=arr[i2].first; int num1=i2-i1; int first1=arr[i2-1].first; cost1+=mid-arr[i1].first; ll cost=cost1; 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; } dp[i1]=min(dp[i1],dp[i+1]+cost); } } return dp[0]; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 856 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 | 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 | 1 ms | 348 KB | Output is correct |
9 | Correct | 1 ms | 348 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 0 ms | 348 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 | 344 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 1 ms | 432 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 344 KB | Output is correct |
3 | Execution timed out | 1050 ms | 5064 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 34 ms | 7108 KB | Output is correct |
4 | Correct | 35 ms | 6604 KB | Output is correct |
5 | Correct | 0 ms | 344 KB | Output is correct |
6 | Correct | 0 ms | 344 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 | 0 ms | 348 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 | 408 KB | Output is correct |
16 | Correct | 0 ms | 348 KB | Output is correct |
17 | Correct | 0 ms | 348 KB | Output is correct |
18 | Correct | 34 ms | 8048 KB | Output is correct |
19 | Correct | 38 ms | 6704 KB | Output is correct |
20 | Correct | 37 ms | 7360 KB | Output is correct |
21 | Correct | 33 ms | 7288 KB | Output is correct |
22 | Correct | 34 ms | 6592 KB | Output is correct |
23 | Correct | 34 ms | 7796 KB | Output is correct |
24 | Correct | 35 ms | 6712 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Execution timed out | 1047 ms | 7880 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 856 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 | 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 | 1 ms | 348 KB | Output is correct |
9 | Correct | 1 ms | 348 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 0 ms | 348 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 | 344 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 1 ms | 432 KB | Output is correct |
17 | Correct | 1 ms | 344 KB | Output is correct |
18 | Correct | 0 ms | 344 KB | Output is correct |
19 | Execution timed out | 1050 ms | 5064 KB | Time limit exceeded |
20 | Halted | 0 ms | 0 KB | - |