Submission #777445

#	Time	Username	Problem	Language	Result	Execution time	Memory
777445		a_aguilo	Sails (IOI07_sails)	C++14	25 / 100	1064 ms	65536 KiB

sails

#include<bits/stdc++.h>

using namespace std;

int N;
long long sol, ans;
const int maxN = 100002;
const int maxH = 100002;
int H[maxN];
int K[maxN];
int occupation[maxH];

void backtracking(int mast, int leftSails, int h){
	if(h == 0){
		if(mast == 0){
			sol = min(sol, ans);
			return;
		}
		else backtracking(mast-1, K[mast-1], H[mast-1]);
	}else{
		if(leftSails == h){
			ans += occupation[h];
			occupation[h]++;
			backtracking(mast, leftSails-1, h-1);
			occupation[h]--;
			ans -= occupation[h];
		}else if(leftSails){
			backtracking(mast, leftSails, h-1);
			ans += occupation[h];
			occupation[h]++;
			backtracking(mast, leftSails-1, h-1);
			occupation[h]--;
			ans -= occupation[h];
		}else{
			backtracking(mast-1, K[mast-1], H[mast-1]);
		}
	}
}

int main(){
	sol = 1e18;
	ans = 0;
	cin >> N;
	for(int i = 1; i <= N; ++i) cin >> H[i] >> K[i];
	backtracking(N, K[N], H[N]);
	cout << sol << endl;
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10