Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- int n;
- int arr[2001], father[2001];
- const int INF = (1 << 20);
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin >> n;
- for(int i = 0; i < n; i ++){
- cin >> arr[i];
- }
- for(int i = 0; i < n; i ++){
- cin >> father[i];
- }
- vector<int> diff;
- int maxDiff = 0;
- for(int i = 0; i < n; i ++){
- if(arr[i] > father[i]){
- diff.push_back(-(arr[i] - father[i]));
- }
- else if(arr[i] < father[i]){
- diff.push_back(abs(arr[i] - father[i]));
- }
- else{
- diff.push_back(0);
- }
- maxDiff = max(maxDiff, abs(arr[i] - father[i]));
- }
- int levo, desno;
- bool znak;
- int mnn;
- int tmplevo, tmpdesno;
- int t = 10;
- bool da;
- long long ret = 0;
- while(true){
- levo = INF;
- desno = -INF;
- tmplevo = INF;
- tmpdesno = -INF;
- for(int i = 0; i < n; i ++){
- if(diff[i] < 0){
- int j = i;
- while(j < n && diff[j] < 0){
- levo = i;
- desno = j;
- j ++;
- }
- if(desno - levo > tmpdesno - tmplevo){
- tmpdesno = desno;
- tmplevo = levo;
- }
- }
- if(diff[i] > 0){
- int j = i;
- while(j < n && diff[j] > 0){
- levo = i;
- desno = j;
- j ++;
- }
- if(desno - levo > tmpdesno - tmplevo){
- tmpdesno = desno;
- tmplevo = levo;
- }
- }
- }
- // cout << tmplevo << " " << tmpdesno << endl;
- mnn = INF;
- for(int i = tmplevo; i <= tmpdesno; i ++){
- mnn = min(mnn, abs(diff[i]));
- }
- for(int i = tmplevo; i <= tmpdesno; i ++){
- int j = mnn;
- while(j --){
- if(diff[i] < 0){
- diff[i] ++;
- }
- else if(diff[i] > 0){
- diff[i] --;
- }
- if(diff[i] == 0)break;
- }
- }
- ret += mnn;
- da = false;
- for(int i =0 ; i < n; i ++){
- if(diff[i] == 0){
- da = true;
- }
- else{
- da = false;
- break;
- }
- }
- if(da)break;
- }
- cout << ret << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment