# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
968754 |
2024-04-24T03:19:36 Z |
12345678 |
Wiring (IOI17_wiring) |
C++17 |
|
1000 ms |
4784 KB |
#include "wiring.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int nx=205;
ll dp[nx][nx];
vector<int> R, B;
ll greedyr(ll x)
{
ll res=LLONG_MAX;
for (auto y:B) res=min(res, abs(x-y));
return res;
}
ll greedyb(ll x)
{
ll res=LLONG_MAX;
for (auto y:R) res=min(res, abs(x-y));
return res;
}
long long min_total_length(std::vector<int> r, std::vector<int> b) {
R=r, B=b;
int n=r.size(), m=b.size();
for (int i=0; i<n; i++)
{
for (int j=0; j<m; j++)
{
dp[i][j]=LLONG_MAX;
if (i>0) dp[i][j]=min(dp[i][j], dp[i-1][j]+greedyr(r[i]));
if (j>0) dp[i][j]=min(dp[i][j], dp[i][j-1]+greedyb(b[j]));
if (i==0&&j==0) dp[i][j]=abs(r[i]-b[j]);
if (i>0&&j>0) dp[i][j]=min(dp[i][j], dp[i-1][j-1]+abs(r[i]-b[j]));
}
}
return dp[n-1][m-1];
}
/*
4 5
1 3 4 5
8 9 10 12 14
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
500 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
18 ms |
864 KB |
Output is correct |
8 |
Correct |
19 ms |
700 KB |
Output is correct |
9 |
Correct |
18 ms |
624 KB |
Output is correct |
10 |
Correct |
18 ms |
604 KB |
Output is correct |
11 |
Correct |
18 ms |
584 KB |
Output is correct |
12 |
Correct |
17 ms |
600 KB |
Output is correct |
13 |
Correct |
17 ms |
604 KB |
Output is correct |
14 |
Correct |
17 ms |
600 KB |
Output is correct |
15 |
Correct |
17 ms |
604 KB |
Output is correct |
16 |
Correct |
17 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
6 ms |
604 KB |
Output is correct |
3 |
Execution timed out |
1037 ms |
3928 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Execution timed out |
1022 ms |
4784 KB |
Time limit exceeded |
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 |
1073 ms |
4180 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
500 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
18 ms |
864 KB |
Output is correct |
8 |
Correct |
19 ms |
700 KB |
Output is correct |
9 |
Correct |
18 ms |
624 KB |
Output is correct |
10 |
Correct |
18 ms |
604 KB |
Output is correct |
11 |
Correct |
18 ms |
584 KB |
Output is correct |
12 |
Correct |
17 ms |
600 KB |
Output is correct |
13 |
Correct |
17 ms |
604 KB |
Output is correct |
14 |
Correct |
17 ms |
600 KB |
Output is correct |
15 |
Correct |
17 ms |
604 KB |
Output is correct |
16 |
Correct |
17 ms |
604 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
6 ms |
604 KB |
Output is correct |
19 |
Execution timed out |
1037 ms |
3928 KB |
Time limit exceeded |
20 |
Halted |
0 ms |
0 KB |
- |