Submission #108145

#	Time	Username	Problem	Language	Result	Execution time	Memory
108145		ami	Krov (COCI17_krov)	C++17	84 / 140	1471 ms	768 KiB

krov

#include <bits/stdc++.h>
#define sz(c)      int(c.size())
#define rep(i,a,b) for (int i=a; i<(b); ++i)
#define per(i,a,b) for (int i=(b)-1; i>=(a); --i)
using namespace std;
using ll = long long;

ll const INF=ll(1e18);
int const MAXN=5500;
int N;
int H[MAXN];

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cout<<fixed<<setprecision(10);

	cin>>N;
	rep(i,0,N) cin>>H[i];
	
	ll res=INF;
	rep(i,0,N) {
		vector<int> a;
		rep(j,0,N) {
			if (j<=i) a.push_back(H[j]+i-j); else a.push_back(H[j]+j-i);
		}
		sort(a.begin(),a.end());
		int X=a[N/2];
		int cor=min(X-i,X-(N-1-i));
		if (cor<=0) X+=1-cor;
		ll sum=0;
		for (int y:a) sum+=abs(X-y);
		res=min(res,sum);
	}
	
	cout<<res<<"\n";
}

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