oj.uz

Submission #48500

# Submission time Handle Problem Language Result Execution time Memory
48500 2018-05-15T06:24:40 Z leehosu01 전봇대 (KOI13_pole) C++17
100 / 100
 34 ms 6452 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
ll tot,eff,midder,VI;
int n;
/*struct A{ll X;ld imp;
    void sc(int i){scanf("%lld",&X);imp=(i?(ld)X/i:0);tot+=X;}
    bool operator<(const A&R)const{return imp==R.imp?X<R.X:imp<R.imp;}
};
vector<A>V;
*/
vector<ll>V;
inline ll mov(ll I,ll gap)
{
   // return abs(V[I].X-I*gap);
    return abs(V[I]-I*gap);
}
inline ll res(ll gap)
{
    int i;
    ll total=0;
    for(i=0;i<n;i++)
        total+=mov(i,gap);
    return total;
}
ll finder(ll l,ll r)
{
    ll leng=1ll<<62;
    for(ll i=l;i<=r;i++)
    {
        leng=min(leng,res(i));
    }
    return leng;
}
int main()
{
    scanf("%d",&n);eff=n;
    V.resize(n);
    int cnt=0;

    for(auto&I:V)scanf("%lld",&I);
   /* for(auto&I:V)I.sc(cnt++);
    sort(V.begin(),V.end());
    */
    ll l=1,m,m1,m2,m3,r=1ll<<32;
    while(l+3<r)
    {
        m=l+r>>1;
        m1=res(m-1);
        m2=res(m);
        m3=res(m+1);
        if(m2<=m3)r=m;
        if(m1>=m2)l=m;
    //printf("%lld %lld %lld %lld ::  %lld %lld \n",m,m1,m2,m3,l,r);
    }
    printf("%lld",finder(l,r));
}

Compilation message

pole.cpp: In function 'int main()':
pole.cpp:49:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         m=l+r>>1;
           ~^~
pole.cpp:40:9: warning: unused variable 'cnt' [-Wunused-variable]
     int cnt=0;
         ^~~
pole.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);eff=n;
     ~~~~~^~~~~~~~~
pole.cpp:42:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(auto&I:V)scanf("%lld",&I);
                  ~~~~~^~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 2 ms 484 KB Output is correct
6 Correct 2 ms 484 KB Output is correct
7 Correct 2 ms 508 KB Output is correct
8 Correct 2 ms 508 KB Output is correct
9 Correct 2 ms 508 KB Output is correct
10 Correct 2 ms 528 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 528 KB Output is correct
2 Correct 2 ms 572 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 2 ms 636 KB Output is correct
6 Correct 2 ms 676 KB Output is correct
7 Correct 2 ms 776 KB Output is correct
8 Correct 2 ms 800 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 824 KB Output is correct
2 Correct 4 ms 824 KB Output is correct
3 Correct 5 ms 996 KB Output is correct
4 Correct 5 ms 1092 KB Output is correct
5 Correct 5 ms 1180 KB Output is correct
6 Correct 6 ms 1236 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2004 KB Output is correct
2 Correct 28 ms 2900 KB Output is correct
3 Correct 33 ms 3792 KB Output is correct
4 Correct 34 ms 4624 KB Output is correct
5 Correct 30 ms 5624 KB Output is correct
6 Correct 28 ms 6452 KB Output is correct