#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((ll)(a).size())
using ll = long long;
const ll infll = (ll)1e18 + 7;
const int N = 2e5 + 5;
struct line_container{
struct line_type{
ll a, b;
mutable ll p;
bool operator< (const line_type& oth) const{
return a < oth.a;
}
bool operator< (ll x) const{
return p < x;
}
};
multiset <line_type, less<>> mts;
const ll inf = infll;
ll div(ll x, ll y){
return x / y - ((x ^ y) < 0 and x % y);
}
template <class T>
bool isect(T x, T y){
if (y == mts.end()){
x->p = infll;
return false;
}
if (x->a == y->a){
x->p = x->b > y->b ? infll : -infll;
}
else{
x->p = div(y->b - x->b, x->a - y->a);
}
return x->p >= y->p;
}
void insert(const line_type& l){
auto z = mts.insert(l), y = z++, x = y;
while (isect(y, z)){
z = mts.erase(z);
}
if (x != mts.begin() and isect(--x, y)){
isect(x, mts.erase(y));
}
while ((y = x) != mts.begin() and (--x)->p >= y->p){
isect(x, mts.erase(y));
}
}
ll query(ll x){
auto l = *mts.lower_bound(x);
return l.a * x + l.b;
}
};
int n, m;
bool col[N];
pair <int, int> pre[N][2];
ll pref[N][2];
ll dp[N];
ll min_total_length(vector <int> r, vector <int> b){
n = isz(r);
m = isz(b);
for (auto pos: r){
col[pos] = true;
}
for (auto pos: b){
col[pos] = false;
}
pre[0][0] = pair{0, 0};
pre[0][1] = pair{0, 0};
ForE(i, 1, n + m){
pre[i][0] = pre[i - 1][0];
pre[i][1] = pre[i - 1][1];
swap(pre[i][col[i]].fi, pre[i][col[i]].se);
pre[i][col[i]].fi = i;
// cout << i << ' ' << pre[i][0].fi << ' ' << pre[i][0].se << ' ' << pre[i][1].fi << ' ' << pre[i][1].se << endl;
}
pref[0][0] = 0;
pref[0][1] = 0;
ForE(i, 1, n + m){
pref[i][0] = pref[i - 1][0] + (col[i] == 0 ? i : 0);
pref[i][1] = pref[i - 1][1] + (col[i] == 1 ? i : 0);
}
fill(dp, dp + n + m + 1, infll);
dp[0] = 0;
ForE(i, 1, n + m){
if (pre[i][0].fi == 0 or pre[i][1].fi == 0){
continue;
}
int j = pre[i][col[i] ^ 1].fi;
dp[i] = min(dp[i], i - j + dp[i - 1]);
int k = pre[j][col[i]].fi;
int leni = i - j, lenj = j - k;
if (leni <= lenj){
ll sum = (pref[i][col[i]] - pref[j][col[i]]) - (pref[j][col[i] ^ 1] - pref[j - leni][col[i] ^ 1]);
for (int l = j - leni; l >= k; l--){
dp[i] = min(dp[i], sum + dp[l]);
sum += (j + 1) - l;
}
}
// cout << i << ' ' << dp[i] << endl;
}
return dp[n + m];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
340 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '1000000000000000007' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
3rd lines differ - on the 1st token, expected: '904', found: '26' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
3rd lines differ - on the 1st token, expected: '316', found: '36' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
276 KB |
Output is correct |
2 |
Correct |
550 ms |
11140 KB |
Output is correct |
3 |
Correct |
21 ms |
11084 KB |
Output is correct |
4 |
Correct |
67 ms |
11148 KB |
Output is correct |
5 |
Correct |
25 ms |
11064 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
312 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
304 KB |
Output is correct |
10 |
Correct |
1 ms |
312 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
308 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
312 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Execution timed out |
1083 ms |
11084 KB |
Time limit exceeded |
19 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
340 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '1000000000000000007' |
2 |
Halted |
0 ms |
0 KB |
- |