oj.uz

Submission #108145

# Submission time Handle Problem Language Result Execution time Memory
108145 2019-04-27T16:25:21 Z ami Krov (COCI17_krov) C++17
84 / 140
 1471 ms 768 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 512 KB Output is correct
2 Correct 59 ms 504 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 432 KB Output is correct
2 Correct 75 ms 384 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 444 KB Output is correct
2 Correct 158 ms 356 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 448 KB Output is correct
2 Correct 207 ms 384 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 512 KB Output is correct
2 Correct 332 ms 444 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1471 ms 384 KB Output is correct
2 Correct 890 ms 384 KB Output is correct
3 Correct 312 ms 384 KB Output is correct

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -