oj.uz

Submission #99060

# Submission time Handle Problem Language Result Execution time Memory
99060 2019-02-28T08:41:12 Z 구재현(#2854, gs14004) Coin Collecting (JOI19_ho_t4) C++17
0 / 100
 69 ms 78712 KB 
#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);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 78584 KB Output is correct
2 Correct 63 ms 78584 KB Output is correct
3 Correct 62 ms 78584 KB Output is correct
4 Correct 69 ms 78584 KB Output is correct
5 Correct 68 ms 78632 KB Output is correct
6 Correct 68 ms 78712 KB Output is correct
7 Correct 66 ms 78584 KB Output is correct
8 Incorrect 67 ms 78584 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 78584 KB Output is correct
2 Correct 63 ms 78584 KB Output is correct
3 Correct 62 ms 78584 KB Output is correct
4 Correct 69 ms 78584 KB Output is correct
5 Correct 68 ms 78632 KB Output is correct
6 Correct 68 ms 78712 KB Output is correct
7 Correct 66 ms 78584 KB Output is correct
8 Incorrect 67 ms 78584 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 78584 KB Output is correct
2 Correct 63 ms 78584 KB Output is correct
3 Correct 62 ms 78584 KB Output is correct
4 Correct 69 ms 78584 KB Output is correct
5 Correct 68 ms 78632 KB Output is correct
6 Correct 68 ms 78712 KB Output is correct
7 Correct 66 ms 78584 KB Output is correct
8 Incorrect 67 ms 78584 KB Output isn't correct
9 Halted 0 ms 0 KB -