# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
406703 |
2021-05-18T03:20:36 Z |
wiwiho |
Wiring (IOI17_wiring) |
C++14 |
|
541 ms |
3520 KB |
#include "wiring.h"
#include<bits/stdc++.h>
#define printv(a, b) { \
for(auto pv : a) b << pv << " "; \
b << "\n"; \
}
#define mp make_pair
#define F first
#define S second
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define eb emplace_back
using namespace std;
typedef long long ll;
using pii = pair<int, int>;
const ll MAX = 1LL << 60;
ostream& operator<<(ostream& o, pii p){
return o << '(' << p.F << ',' << p.S << ')';
}
ll min_total_length(vector<int> r, vector<int> b) {
int n = r.size(), m = b.size();
assert(n <= 200);
vector<pii> a;
for(int i : r) a.eb(mp(i, 0));
for(int i : b) a.eb(mp(i, 1));
lsort(a);
vector<vector<ll>> dp(n + m + 1, vector<ll>(n + m + 1, MAX));
dp[0][0] = 0;
ll lst = a[0].F;
for(pii now : a){
vector<vector<ll>> dp2(n + m + 1, vector<ll>(n + m + 1, MAX));
for(int i = 0; i <= n + m; i++){
for(int j = 0; j <= n + m; j++){
if(dp[i][j] == MAX) continue;
dp[i][j] += (ll)(i + j) * (now.F - lst);
}
}
if(now.S == 0){
for(int i = 0; i <= n + m; i++){
for(int j = n + m; j > 0; j--){
dp2[i][j - 1] = min({dp2[i][j - 1], dp[i][j], dp2[i][j]});
}
}
for(int i = 0; i < n + m; i++){
for(int j = 0; j <= n + m; j++){
dp2[i + 1][j] = min({dp2[i + 1][j], dp[i][j], dp2[i][j]});
}
}
}
else{
for(int i = n + m; i > 0; i--){
for(int j = 0; j <= n + m; j++){
dp2[i - 1][j] = min({dp2[i - 1][j], dp[i][j], dp2[i][j]});
}
}
for(int i = 0; i <= n + m; i++){
for(int j = 0; j < n + m; j++){
dp2[i][j + 1] = min({dp2[i][j + 1], dp[i][j], dp2[i][j]});
}
}
}
dp = dp2;
lst = now.F;
//cerr << "test " << now.F << " " << now.S << "\n";
//for(int i = 0; i <= n; i++) printv(dp[i], cerr);
}
return dp[0][0];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
2 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
456 ms |
2972 KB |
Output is correct |
8 |
Correct |
454 ms |
2980 KB |
Output is correct |
9 |
Correct |
491 ms |
3060 KB |
Output is correct |
10 |
Correct |
469 ms |
3048 KB |
Output is correct |
11 |
Correct |
541 ms |
2852 KB |
Output is correct |
12 |
Correct |
460 ms |
2836 KB |
Output is correct |
13 |
Correct |
463 ms |
2932 KB |
Output is correct |
14 |
Correct |
450 ms |
2976 KB |
Output is correct |
15 |
Correct |
452 ms |
2964 KB |
Output is correct |
16 |
Correct |
484 ms |
2956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
179 ms |
1648 KB |
Output is correct |
3 |
Runtime error |
25 ms |
2796 KB |
Execution killed with signal 6 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Runtime error |
29 ms |
3496 KB |
Execution killed with signal 6 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Runtime error |
25 ms |
3520 KB |
Execution killed with signal 6 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
2 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
456 ms |
2972 KB |
Output is correct |
8 |
Correct |
454 ms |
2980 KB |
Output is correct |
9 |
Correct |
491 ms |
3060 KB |
Output is correct |
10 |
Correct |
469 ms |
3048 KB |
Output is correct |
11 |
Correct |
541 ms |
2852 KB |
Output is correct |
12 |
Correct |
460 ms |
2836 KB |
Output is correct |
13 |
Correct |
463 ms |
2932 KB |
Output is correct |
14 |
Correct |
450 ms |
2976 KB |
Output is correct |
15 |
Correct |
452 ms |
2964 KB |
Output is correct |
16 |
Correct |
484 ms |
2956 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
179 ms |
1648 KB |
Output is correct |
19 |
Runtime error |
25 ms |
2796 KB |
Execution killed with signal 6 |
20 |
Halted |
0 ms |
0 KB |
- |