| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1036359 |
2024-07-27T09:45:30 Z |
beaconmc |
Wiring (IOI17_wiring) |
C++14 |
|
523 ms |
262144 KB |
#include "wiring.h"
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
using namespace std;
ll n,m;
vector<ll> R,B;
unordered_map<ll, ll> cache;
ll dp(ll x, ll y){
if (abs(x-y) > 300) return 1000000000000000;
if (cache.count(x*1000000+y)) return cache[x*1000000+y];
if (x==n && y==m) return 0;
if (x>=n || y >= m) return 1000000000000000;
return cache[x*1000000+y] = min(dp(x+1,y), min(dp(x,y+1), dp(x+1,y+1))) + abs(R[x] - B[y]);
}
long long min_total_length(std::vector<int> r, std::vector<int> b) {
R.clear();
B.clear();
cache.clear();
for (auto&i : r) R.push_back(i);
for (auto&i : b) B.push_back(i);
n = r.size();
m = b.size();
return dp(0,0);
}
| # |
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 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
3 ms |
1976 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1976 KB |
Output is correct |
| 9 |
Correct |
3 ms |
1976 KB |
Output is correct |
| 10 |
Correct |
4 ms |
1976 KB |
Output is correct |
| 11 |
Correct |
3 ms |
1976 KB |
Output is correct |
| 12 |
Correct |
4 ms |
1976 KB |
Output is correct |
| 13 |
Correct |
3 ms |
1976 KB |
Output is correct |
| 14 |
Correct |
4 ms |
1976 KB |
Output is correct |
| 15 |
Correct |
3 ms |
1976 KB |
Output is correct |
| 16 |
Correct |
3 ms |
1976 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 3 |
Runtime error |
506 ms |
262144 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Runtime error |
523 ms |
262144 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
518 ms |
262144 KB |
Execution killed with signal 9 |
| 3 |
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 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
3 ms |
1976 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1976 KB |
Output is correct |
| 9 |
Correct |
3 ms |
1976 KB |
Output is correct |
| 10 |
Correct |
4 ms |
1976 KB |
Output is correct |
| 11 |
Correct |
3 ms |
1976 KB |
Output is correct |
| 12 |
Correct |
4 ms |
1976 KB |
Output is correct |
| 13 |
Correct |
3 ms |
1976 KB |
Output is correct |
| 14 |
Correct |
4 ms |
1976 KB |
Output is correct |
| 15 |
Correct |
3 ms |
1976 KB |
Output is correct |
| 16 |
Correct |
3 ms |
1976 KB |
Output is correct |
| 17 |
Correct |
0 ms |
348 KB |
Output is correct |
| 18 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 19 |
Runtime error |
506 ms |
262144 KB |
Execution killed with signal 9 |
| 20 |
Halted |
0 ms |
0 KB |
- |
