제출 #8093

#제출 시각아이디문제언어결과실행 시간메모리
8093gs14004전봇대 (KOI13_pole)C++98
89 / 100
60 ms2648 KiB
#include <cstdio> #include <algorithm> using namespace std; typedef long long lint; struct pole{lint a,i;}d[100005]; int cmp(pole a, pole b){return a.a * b.i < b.a * a.i;} lint n; lint trial(lint piv){ lint res = 0; for (int i=0; i<n; i++) { res += max(d[i].a - piv * d[i].i, piv * d[i].i - d[i].a); } return res; } int main(){ scanf("%lld",&n); for (int i=0; i<n; i++) { scanf("%lld",&d[i].a); d[i].i = i; } sort(d,d+n,cmp); int piv; lint cum = 0; for (piv = 0; piv < n; piv++) { cum += d[piv].i; if(cum >= n * (n-1) / 4) break; } lint that = d[piv].a / d[piv].i; printf("%lld",min(min(trial(that-1),trial(that)),trial(that+1))); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...