#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
using lint = long long;
using pi = pair<int, int>;
struct pnt{
int x, y;
bool operator<(const pnt &p)const{
return pi(x, y) < pi(p.x, p.y);
}
}a[MAXN];
int n;
int cnt[3][MAXN];
lint dp[MAXN][50];
lint sum(int x){ return 1ll * x * (x + 1) / 2; }
lint sum_intv(int l, int r, int x){
if(l <= x && x < r){
return sum(x - l) + sum(r - 1 - x);
}
if(x >= r) return sum(x - l) - sum(x - r);
return sum(r - x - 1) - sum(l - x - 1);
}
int thres[MAXN];
map<pi, lint> mp;
bool insec(int l, int r, int ll, int rr){
return max(l, ll) <= min(r, rr);
}
lint f(int l, int r, int pos){
if(pos == n + 1) return l == r ? 0 : 1e18;
if(cnt[1][pos] == 0 && cnt[2][pos] == 0) return f(l, r, pos + 1);
if(mp.find(pi(l, r)) != mp.end()) return mp[pi(l, r)];
int up = cnt[1][pos];
int dn = cnt[2][pos];
lint ret = 1e18;
for(int i=0; i<=up+dn; i++){
int nl = l + i, nr = up + dn - i + r;
if(nl > n + 1 || nr > n + 1) continue;
if(i > 0 && i < up + dn && !insec(l, nl, r, nr)) continue;
lint cost = f(nl, nr, pos + 1);
cost += abs(up - (nl - l));
cost += sum_intv(l, nl, pos);
cost += sum_intv(r, nr, pos);
ret = min(ret, cost);
}
return mp[pi(l, r)] = ret;
}
int main(){
scanf("%d",&n);
memset(dp, -1, sizeof(dp));
lint cdap = 0;
for(int i=0; i<n*2; i++){
scanf("%d %d",&a[i].x,&a[i].y);
if(a[i].x < 1){
cdap += 1 - a[i].x;
a[i].x = 1;
}
if(a[i].x > n){
cdap += a[i].x - n;
a[i].x = n;
}
if(a[i].y < 1){
cdap += 1 - a[i].y;
a[i].y = 1;
}
if(a[i].y > 2){
cdap += a[i].y - 2;
a[i].y = 2;
}
cnt[a[i].y][a[i].x]++;
}
for(int i=1; i<=n; i++){
for(int j=-2; j<=2; j++){
if(i + j >= 1 && i + j <= n){
thres[i] += cnt[1][i+j] + cnt[2][i+j];
}
}
}
sort(a, a + n + n);
cout << cdap + f(1, 1, 1) << endl;
}
Compilation message
joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
joi2019_ho_t4.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&a[i].x,&a[i].y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
78592 KB |
Output is correct |
| 2 |
Correct |
68 ms |
78664 KB |
Output is correct |
| 3 |
Correct |
67 ms |
78584 KB |
Output is correct |
| 4 |
Correct |
67 ms |
78588 KB |
Output is correct |
| 5 |
Correct |
69 ms |
78584 KB |
Output is correct |
| 6 |
Correct |
68 ms |
78584 KB |
Output is correct |
| 7 |
Correct |
76 ms |
78584 KB |
Output is correct |
| 8 |
Correct |
75 ms |
78584 KB |
Output is correct |
| 9 |
Incorrect |
78 ms |
78616 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
78592 KB |
Output is correct |
| 2 |
Correct |
68 ms |
78664 KB |
Output is correct |
| 3 |
Correct |
67 ms |
78584 KB |
Output is correct |
| 4 |
Correct |
67 ms |
78588 KB |
Output is correct |
| 5 |
Correct |
69 ms |
78584 KB |
Output is correct |
| 6 |
Correct |
68 ms |
78584 KB |
Output is correct |
| 7 |
Correct |
76 ms |
78584 KB |
Output is correct |
| 8 |
Correct |
75 ms |
78584 KB |
Output is correct |
| 9 |
Incorrect |
78 ms |
78616 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
78592 KB |
Output is correct |
| 2 |
Correct |
68 ms |
78664 KB |
Output is correct |
| 3 |
Correct |
67 ms |
78584 KB |
Output is correct |
| 4 |
Correct |
67 ms |
78588 KB |
Output is correct |
| 5 |
Correct |
69 ms |
78584 KB |
Output is correct |
| 6 |
Correct |
68 ms |
78584 KB |
Output is correct |
| 7 |
Correct |
76 ms |
78584 KB |
Output is correct |
| 8 |
Correct |
75 ms |
78584 KB |
Output is correct |
| 9 |
Incorrect |
78 ms |
78616 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
