Submission #368391

# Submission time Handle Problem Language Result Execution time Memory
368391 2021-02-20T02:31:27 Z xuannhiminh Krov (COCI17_krov) C++14
70 / 140
1500 ms 2156 KB
#include <bits/stdc++.h>
using namespace std;
#define int long long

int maOf (int a, int b)
{
return (a>b) ? a : b;
}
int miOf (int a, int b)
{
return (a<b) ? a : b;
}
int tong(int a[], int n,int i, int m){
   int y = m;
    int d = 0;
d += abs(a[i] - y);
    y--;
for(int j = i - 1; j >= 1; j--){
   d += abs(a[j] - y);
   y--;
    }
	y = m - 1;
    for(int j = i + 1; j <= n; j++){
   d += abs(a[j] - y);
   y--;
    }
    return d;
}
 
int roof(int *a, int &n,int &i){
int t, p= 1e9,average,tog,tong2,tong3,tong4,tong5;
if(n&1) t = maOf(i, n - i);
else t = maOf(i, n - i) + 1;
    while(p > t + 1){
         average = (t + p)/2;
tog = tong(a,n,i, t);
        tong2 = tong(a,n,i, average); tong3 = tong(a,n,i, p);
		 if(tog > tong2 && tong2 > tong3){
            t = average;
        }else {
    if(tog < tong2 && tong2 < tong3){
                p = average;
            }
      else {
tong4 = tong(a,n,i, average - 1);tong5 = tong(a,n,i, average + 1);
if(tong4 > tong2 && tong2 > tong5) t = average;
else p = average;
            }
        }
    }
    return miOf(tong(a,n,i, t), tong(a,n,i, p));
}
 
main (){
int n,kq=1e12,y;
    cin>>(n); int a[n+1];
for(int i = 1; i <= n; i++) 
	cin>>(a[i]);
for(int i = 1; i <= n; i++){
y = roof(a,n,i);
        if(kq > y) {
            kq = y;
        }
    }
    cout<<(kq);
}

Compilation message

krov.cpp:54:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   54 | main (){
      |       ^
# Verdict Execution time Memory Grader output
1 Correct 45 ms 364 KB Output is correct
2 Correct 53 ms 512 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 48 ms 512 KB Output is correct
2 Correct 64 ms 364 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 128 ms 384 KB Output is correct
2 Correct 136 ms 492 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 272 ms 364 KB Output is correct
2 Correct 338 ms 492 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 465 ms 492 KB Output is correct
2 Correct 303 ms 364 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 1551 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1561 ms 620 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1578 ms 876 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1586 ms 1516 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1576 ms 2156 KB Time limit exceeded
2 Halted 0 ms 0 KB -