| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1051341 |
2024-08-10T04:50:08 Z |
pawned |
Wiring (IOI17_wiring) |
C++17 |
|
162 ms |
6196 KB |
#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
#include "wiring.h"
ll min_total_length(vector<int> r_g, vector<int> b_g) {
vi r, b;
for (int x : r_g)
r.pb(x);
for (int x : b_g)
b.pb(x);
int N = r.size();
int M = b.size();
map<int, ll> dp;
// dp[i][j]: min cost to connect first i red (exclusive)
// with first j blue (exclusive)
dp[0] = 0;
for (int i = 1; i <= N; i++) {
// cout<<"at "<<i<<endl;
map<int, ll> newdp;
// consider only up to previous blue minus 10, next blue plus 10
auto it = lower_bound(b.begin(), b.end(), r[i - 1]);
int lb = max(1, (int)(it - b.begin()) - 10);
int rb = min(M, (int)(it - b.begin()) + 10);
for (int j = lb; j <= rb; j++) { // only consider up to consec
// cout<<"j: "<<j<<endl;
newdp[j] = 1e18;
if (newdp.find(j - 1) != newdp.end())
newdp[j] = min(newdp[j], newdp[j - 1] + abs(r[i - 1] - b[j - 1]));
if (dp.find(j) != dp.end())
newdp[j] = min(newdp[j], dp[j] + abs(r[i - 1] - b[j - 1]));
if (dp.find(j - 1) != dp.end())
newdp[j] = min(newdp[j], dp[j - 1] + abs(r[i - 1] - b[j - 1]));
}
dp = newdp;
/* cout<<"dp: "<<endl;
for (pair<int, ll> p : dp)
cout<<p.fi<<": "<<p.se<<endl;*/
}
return dp[M];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '14340', found: '1000000000000000000' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '904', found: '0' |
| 2 |
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 |
160 ms |
4160 KB |
Output is correct |
| 4 |
Correct |
158 ms |
5836 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 |
344 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
0 ms |
348 KB |
Output is correct |
| 17 |
Correct |
1 ms |
344 KB |
Output is correct |
| 18 |
Correct |
162 ms |
6196 KB |
Output is correct |
| 19 |
Correct |
159 ms |
6096 KB |
Output is correct |
| 20 |
Correct |
159 ms |
6092 KB |
Output is correct |
| 21 |
Correct |
158 ms |
6096 KB |
Output is correct |
| 22 |
Correct |
162 ms |
6096 KB |
Output is correct |
| 23 |
Correct |
160 ms |
6096 KB |
Output is correct |
| 24 |
Correct |
160 ms |
6096 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
155 ms |
4164 KB |
3rd lines differ - on the 1st token, expected: '373710605', found: '0' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '14340', found: '1000000000000000000' |
| 3 |
Halted |
0 ms |
0 KB |
- |
