Submission #702939

#	Time	Username	Problem	Language	Result	Execution time	Memory
702939		Abrar_Al_Samit	Wiring (IOI17_wiring)	C++17	0 / 100	1 ms	316 KiB

wiring

#include<bits/stdc++.h>
using namespace std;

const int nax = 203;

vector<int>red, blue;
int n, m;
long long dp[nax][nax];

long long solve(int i, int j) {
	if(i>=n && j>=m) return 0LL;
	long long &ret = dp[i][j];
	if(ret!=-1) return ret;
	ret = 1e18;

	if(i<n && j<m) ret = solve(i+1, j+1) + abs(red[i]-blue[j]);
	if(i>0 && j<m) ret = min(ret, solve(i, j+1) + abs(red[i-1]-blue[j]));
	if(j>0 && i<n) ret = min(ret, solve(i+1, j) + abs(red[i]-blue[j-1]));
	return ret;
}
long long min_total_length(vector<int>r, vector<int>b) {
	n = r.size(), m = b.size();
	red = r, blue = b;

	long long ans = 0;
	for(int i=0; i<n; ++i) {
		ans += abs(red[i]-red[n-1]);
	}
	for(int i=0; i<m; ++i) {
		ans += abs(blue[i]-red[n-1]);
	}
	return ans;

	int lefr[n], ritr[n];

	int p = -1;
	for(int i=0; i<n; ++i) {
		while(p+1<m && b[p+1]<r[i]) ++p;
		lefr[i] = p;		
	}
	p = m;
	for(int i=n-1; i>=0; --i) {
		while(p-1>=0 && b[p-1]>r[i]) --p;
		ritr[i] = p;
	}

	int lefb[m], ritb[m];
	p = -1;
	for(int i=0; i<m; ++i) {
		while(p+1<n && r[p+1]<b[i]) ++p;
		lefb[i] = p;
	}
	p = n;
	for(int i=m-1; i>=0; --i) {
		while(p-1>=0 && r[p-1]>b[i]) --p;
		ritb[i] = p;
	}

	vector<array<int, 3>>edges;
	for(int i=0; i<n; ++i) {

	}
	for(int i=0; i<m; ++i) {

	}

	sort(edges.begin(), edges.end());

}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:34:6: warning: variable 'lefr' set but not used [-Wunused-but-set-variable]
   34 |  int lefr[n], ritr[n];
      |      ^~~~
wiring.cpp:34:15: warning: variable 'ritr' set but not used [-Wunused-but-set-variable]
   34 |  int lefr[n], ritr[n];
      |               ^~~~
wiring.cpp:47:6: warning: variable 'lefb' set but not used [-Wunused-but-set-variable]
   47 |  int lefb[m], ritb[m];
      |      ^~~~
wiring.cpp:47:15: warning: variable 'ritb' set but not used [-Wunused-but-set-variable]
   47 |  int lefb[m], ritb[m];
      |               ^~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45