oj.uz

Submission #990429

# Submission time Handle Problem Language Result Execution time Memory
990429 2024-05-30T11:48:50 Z StefanSebez Wiring (IOI17_wiring) C++14
13 / 100
 18 ms 1996 KB 
#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
const ll inf=1e18;
long long min_total_length(std::vector<int> r, std::vector<int> b) {
	int n=r.size(),m=b.size();
	ll res=0;
	bool subtask2=false;if(r.back()<b[0]) subtask2=true;
	if(subtask2){
		for(int i=n-1,j=m-1;i>=0 || j>=0;){
			if(i==-1 && j>0){
				while(j>=0){
					res+=b[j]-r[n-1];
					j--;
				}
				break;
			}
			else if(i>0 && j==-1){
				while(i>=0){
					res+=b[0]-r[i];
					i--;
				}
				break;
			}
			else{
				res+=b[j]-r[i];
				j--;
				i--;
			}
		}
	}
	else{
		if(n>m){
			swap(n,m);
			swap(r,b);
		}
		int A[n+10],B[m+10];
		for(int i=0;i<n;i++) A[i+1]=r[i];
		for(int i=0;i<m;i++) B[i+1]=b[i];
		ll dp[m+1][n+1];
		for(ll i=1,cost=0;i<=m;i++){
			cost+=abs(A[1]-B[i]);
			dp[i][1]=cost;
		}
		dp[0][1]=inf;
		for(int j=2;j<=n;j++){
			for(int i=0;i<=m;i++){
				dp[i][j]=inf;
				if(i<j) continue;
				for(ll k=i-1,cost=0;k>=0;k--){
					cost+=abs(A[j]-B[k+1]);
					dp[i][j]=min(dp[i][j],dp[k][j-1]+cost);
				}
			}
		}
		/*for(int j=1;j<=n;j++){
			printf("%i: ",j);
			for(int i=0;i<=m;i++){
				printf("%lld ",dp[i][j]);
			}
			printf("\n");
		}*/
		res=dp[m][n];
	}
	return res;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB 3rd lines differ - on the 1st token, expected: '14340', found: '17422'
3 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 18 ms 1496 KB Output is correct
4 Correct 12 ms 1628 KB Output is correct
5 Correct 14 ms 1372 KB Output is correct
6 Correct 18 ms 1884 KB Output is correct
7 Correct 15 ms 1884 KB Output is correct
8 Correct 16 ms 1996 KB Output is correct
9 Correct 15 ms 1996 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB 3rd lines differ - on the 1st token, expected: '17703', found: '19052'
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

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

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB 3rd lines differ - on the 1st token, expected: '14340', found: '17422'
3 Halted 0 ms 0 KB -