oj.uz

Submission #1044574

# Submission time Handle Problem Language Result Execution time Memory
1044574 2024-08-05T10:59:33 Z Hugo1729 Wiring (IOI17_wiring) C++11
0 / 100
 30 ms 8748 KB 
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll dp[200001]={0};
ll pref[200001]={0};

ll min_total_length(vector<int> r, vector<int> b) {
	int n=r.size(),m=b.size();

	vector<pair<int,int>> a;
	for(int v : r)a.push_back({v,0});
	for(int v : b)a.push_back({v,1});

	sort(a.begin(),a.end());
	for(int i=0;i<n+m;i++){
		pref[i+1]=pref[i]+a[i].first;
	}
	// for(int i=0;i<n+m;i++)cout << a[i].first << ' ';
	// cout << '\n';
	// for(int i=0;i<=n+m;i++)cout << pref[i] << ' ';
	// cout << '\n';

	int prev_begin=-1,prev_end=-1;

	for(int i=1;i<n+m;i++){
		if(a[i].second!=a[i-1].second){
			prev_begin=prev_end+1;
			prev_end=i-1;
		}

		if(prev_begin==-1)continue;

		if(prev_begin==0){
			dp[i]=LLONG_MAX/4;

			int x=(prev_end-prev_begin+1),y=i-prev_end;

			
			if(x<=y){
				dp[i]=(a[prev_end].first*x-pref[prev_end+1])+(pref[i+1]-pref[prev_end+1]-a[prev_end].first*y);
				// cout << i << ' ' << prev_begin << ' ' << prev_end << ' ' << "a: " << (a[prev_end].first*x-pref[prev_end+1]) << ' ' << (pref[i+1]-pref[prev_end+1]-a[prev_end].first*y) << '\n';
			}else{
				dp[i]=(a[prev_end+1].first*x-pref[prev_end+1])+(pref[i+1]-pref[prev_end+1]-a[prev_end+1].first*y);
				// cout << i << ' ' << prev_begin << ' ' << prev_end << ' ' <<  "b: " << (a[prev_end+1].first*x-pref[prev_end+1]) << ' ' << (pref[i+1]-pref[prev_end+1]-a[prev_end+1].first*y) << '\n';
			}
			continue;
		}

		dp[i]=LLONG_MAX/4;

		for(int j=prev_begin;j<=prev_end;j++){

			int x=(prev_end-j+1),y=i-prev_end;

			
			if(x<=y){
				dp[i]=min(dp[i],(a[prev_end].first*x-(pref[prev_end+1]-pref[j]))+(pref[i+1]-pref[prev_end+1]-a[prev_end].first*y)+dp[j-1]);
				// cout << i << ' ' << prev_begin << ' ' << prev_end << ' ' << "a: " << (a[prev_end].first*x-pref[prev_end+1]) << ' ' << (pref[i+1]-pref[prev_end+1]-a[prev_end].first*y) << '\n';
			}else{
				dp[i]=min(dp[i],(a[prev_end+1].first*x-(pref[prev_end+1]-pref[j]))+(pref[i+1]-pref[prev_end+1]-a[prev_end+1].first*y)+dp[j-1]);
				// cout << i << ' ' << prev_begin << ' ' << prev_end << ' ' <<  "b: " << (a[prev_end+1].first*x-pref[prev_end+1]) << ' ' << (pref[i+1]-pref[prev_end+1]-a[prev_end+1].first*y) << '\n';
			}
		}
	}

	// cout << "\n\n";
	// for(int i=0;i<n+m;i++)cout << dp[i] << ' ';
	// cout << "\n\n";



	return dp[n+m-1];
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB 3rd lines differ - on the 1st token, expected: '25859', found: '21937'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Incorrect 15 ms 6764 KB 3rd lines differ - on the 1st token, expected: '41596985758595', found: '8388298625923'
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Incorrect 30 ms 8748 KB 3rd lines differ - on the 1st token, expected: '1068938599', found: '-65977857131596'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB 3rd lines differ - on the 1st token, expected: '27', found: '23'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB 3rd lines differ - on the 1st token, expected: '25859', found: '21937'
2 Halted 0 ms 0 KB -