Submission #90288

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
90288	2018-12-21T05:24:00 Z	mirbek01	Mountain Trek Route (IZhO12_route)	C++17	0 / 100	2 ms	624 KB

route

# include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 2;

int n, k, a[N];
long long bg = 0, cur = 0;

int main(){
      scanf("%d %d", &n, &k);

      for(int i = 1; i <= n; i ++){
            scanf("%d", a + i);
      }

      for(int i = 1; i <= n; i ++){
            int nxt = i + 1;
            if(nxt > n)
                  nxt = 1;
            if(n > 2 || i == 1)
                  bg += abs(a[i] - a[nxt]);
      }

      if(n > 2){
            for(int i = 1; i <= n; i ++){
                  int pre = i - 1, nxt = i + 1;
                  if(pre < 1)
                        pre = n;
                  if(nxt > n)
                        nxt = 1;
                  if(a[i] < a[pre] && a[i] < a[nxt]){
                        int mn = min(k, min(a[pre], a[nxt]) - a[i]);
                        a[i] += mn;
                        k -= mn;
                  }
            }
      }

      int lo = 1, hi = 1e9, m;

      while(lo <= hi){
            int md = (lo + hi) >> 1;
            long long cnt = 0;
            for(int i = 1; i <= n; i ++){
                  if(a[i] < md)
                        cnt += md - a[i];
            }
            if(cnt <= k)
                  lo = md + 1, m = md;
            else
                  hi = md - 1;
      }



      for(int i = 1; i <= n; i ++)
            a[i] = max(a[i], m);

      for(int i = 1; i <= n; i ++){
            int nxt = i + 1;
            if(nxt > n)
                  nxt = 1;
            if(n > 2 || i == 1)
                  cur += abs(a[i] - a[nxt]);
      }

      cout << bg - cur << endl;
}

Compilation message

route.cpp: In function 'int main()':
route.cpp:11:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &n, &k);
       ~~~~~^~~~~~~~~~~~~~~~~
route.cpp:14:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", a + i);
             ~~~~~^~~~~~~~~~~~~
route.cpp:40:29: warning: 'm' may be used uninitialized in this function [-Wmaybe-uninitialized]
       int lo = 1, hi = 1e9, m;
                             ^

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	372 KB	Output is correct
3	Correct	2 ms	448 KB	Output is correct
4	Correct	2 ms	468 KB	Output is correct
5	Correct	2 ms	552 KB	Output is correct
6	Incorrect	2 ms	624 KB	Output isn't correct
7	Halted	0 ms	0 KB	-