# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
883911 | 2023-12-06T11:34:59 Z | JakobZorz | 전선 연결 (IOI17_wiring) | C++14 | 1000 ms | 8540 KB |
#include"wiring.h" #include<iostream> #include<algorithm> #include<set> using namespace std; typedef long long ll; const int TREE_SIZE=1<<18; ll tree[TREE_SIZE]; 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; int first1=arr[i2-1].first; for(int i=i2;i<i3;i++) tree[i]=arr[i].first-first1; } if(i2==dp.size()-1) continue; int mid=arr[i2].first; int num1=i2-i1; cost1+=mid-arr[i1].first; dp[i1]=dp[i2]; tree[2*i2-i1-1]=arr[2*i2-i1-1].first-mid; /*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); }*/ ll cost=0; for(int i=i2;i<i3;i++){ cost+=tree[i]; dp[i1]=min(dp[i1],dp[i+1]+cost); } dp[i1]+=cost1; } return dp[0]; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 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 | 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 | 348 KB | Output is correct |
16 | Correct | 0 ms | 348 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Execution timed out | 1074 ms | 5068 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 34 ms | 6792 KB | Output is correct |
4 | Correct | 42 ms | 6764 KB | Output is correct |
5 | Correct | 0 ms | 600 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 | 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 | 344 KB | Output is correct |
14 | Correct | 1 ms | 536 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 1 ms | 348 KB | Output is correct |
17 | Correct | 0 ms | 352 KB | Output is correct |
18 | Correct | 36 ms | 6828 KB | Output is correct |
19 | Correct | 34 ms | 7628 KB | Output is correct |
20 | Correct | 37 ms | 6788 KB | Output is correct |
21 | Correct | 34 ms | 6596 KB | Output is correct |
22 | Correct | 38 ms | 8132 KB | Output is correct |
23 | Correct | 35 ms | 7108 KB | Output is correct |
24 | Correct | 34 ms | 8540 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Execution timed out | 1056 ms | 6708 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 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 | 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 | 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 | 348 KB | Output is correct |
19 | Execution timed out | 1074 ms | 5068 KB | Time limit exceeded |
20 | Halted | 0 ms | 0 KB | - |