# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
34674 | 2017-11-14T22:27:24 Z | mohammad_kilani | Wiring (IOI17_wiring) | C++14 | 36 ms | 5148 KB |
#include "wiring.h" #include <bits/stdc++.h> using namespace std; #define red 1 #define blue 0 const int N = 200010; long long dp[N]; vector< pair<int,bool> > v; int n; long long solve(int i){ if(i == n) return 0; if(dp[i] != -1) return dp[i]; dp[i] = 1e18; int idx = -1; for(int j=i+1;j<n;j++){ if(v[j].second != v[i].second){ idx = j; break; } } if(idx == -1) return dp[i]; long long sum = 0; for(int j=i;j<idx;j++) sum += abs(v[idx].first - v[j].first); int idx2 = n; for(int j=idx+1;j<n;j++){ if(v[i].second == v[idx].second){ idx2 = j; break; } } for(int j=idx;j<idx2;j++){ sum+= abs(v[j].first - v[idx].first); if(j - idx >= idx - i) sum += abs(v[idx].first - v[idx-1].first); dp[i] = min(dp[j],sum + solve(j+1)); } for(int j=idx2;j<n;j++){ if(v[j].second == v[idx].second) break; sum+= abs(v[j].first-v[idx].first); dp[i] = min(dp[i],sum + solve(j+1)); } return dp[i]; } long long min_total_length(std::vector<int> r, std::vector<int> b) { if(r.back() < b[0]){ int n =r.size() , m = b.size(); long long sum = 0 ; int idx = 0 ; int idx2 = 0; for(int i=0;i<min(n,m);i++) sum += abs(r[idx++] - b[idx2++]); for(int i=idx;i<r.size();i++) sum+= abs(r[i] - b[0]); for(int i=idx2;i<b.size();i++) sum+= abs(b[i] - r.back()); return sum; } memset(dp,-1,sizeof(dp)); int j =0 ; for(int i=0;i<r.size();i++){ while(j < b.size() && b[j] < r[i]) v.push_back(make_pair(b[j++],blue)); v.push_back(make_pair(r[i],red)); } while(j < b.size()) v.push_back(make_pair(b[j++],blue)); n = v.size(); return solve(0); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 3580 KB | 3rd lines differ - on the 1st token, expected: '25859', found: '53243' |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 3580 KB | Output is correct |
2 | Correct | 0 ms | 3580 KB | Output is correct |
3 | Correct | 26 ms | 4756 KB | Output is correct |
4 | Correct | 26 ms | 4756 KB | Output is correct |
5 | Correct | 33 ms | 4756 KB | Output is correct |
6 | Correct | 33 ms | 5148 KB | Output is correct |
7 | Correct | 33 ms | 5148 KB | Output is correct |
8 | Correct | 36 ms | 5148 KB | Output is correct |
9 | Correct | 36 ms | 5148 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 3580 KB | Output is correct |
2 | Incorrect | 0 ms | 3580 KB | 3rd lines differ - on the 1st token, expected: '17703', found: '24640' |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 3580 KB | 3rd lines differ - on the 1st token, expected: '27', found: '142' |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 3580 KB | 3rd lines differ - on the 1st token, expected: '25859', found: '53243' |
2 | Halted | 0 ms | 0 KB | - |