답안 #90311

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
90311	2018-12-21T08:29:51 Z	mirbek01	등산 경로 (IZhO12_route)	C++17	0 / 100	322 ms	66560 KB

route

# include <bits/stdc++.h>

# define int long long

using namespace std;

const int N = 1e6 + 5;

int n, k, a[N], p[N], sz[N], L[N], bg, cur;
set < pair <int, int> >  s;

int f_s(int v){
      if(v < 1){
            v = n;
      }
      if(v > n){
            v = 1;
      }
      return p[v] == v?v:p[v] = f_s(p[v]);
}

void u_s(int x, int y){
      x = f_s(x);
      y = f_s(y);
      if(x != y){
            p[x] = y;
            sz[y] += sz[x];
            L[y] = L[x];
      }
}

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

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

      bool ok = 1;

      for(int i = 1; i <= n; i ++){
            if(a[i] != a[1])
                  ok = 0;
      }

      if(ok){
            puts("0");
            return 0;
      }

      if(n == 2){
           bg = abs(a[2] - a[1]);
           if(a[1] < a[2]){
                  a[1] += k;
                  a[1] = min(a[2], a[1]);
            } else {
                  a[2] += k;
                  a[2] = min(a[2], a[1]);
            }
            cur = abs(a[2] - a[1]);
            cout << bg - cur << endl;
            return 0;
      }

      for(int i = 1; i <= n; i ++){
            int nxt = i + 1;
            if(nxt > n)
                  nxt = 1;
            bg += abs(a[i] - a[nxt]);
            p[i] = i, sz[i] = 1;
            L[i] = i;
      }

      for(int i = 1; i <= n; i ++){
            int pre = i - 1;
            if(pre < 1)
                  pre = n;
            if(a[i] == a[pre])
                  u_s(pre, i);
      }

      for(int i = 1; i <= n; i ++)
            s.insert({sz[f_s(i)], f_s(i)});

      while(!s.empty() && k > 0){
            pair <int, int> p = *s.begin();
            s.erase(s.begin());
            int l = f_s(L[p.second] - 1), r = f_s(p.second + 1);
            if(a[l] <= a[p.second] || a[r] <= a[p.second])
                  continue;
            int mn = min(k / sz[p.second], min(a[l], a[r]) - a[p.second]);
            k -= mn * sz[p.second];
            a[p.second] += mn;
            int presz = sz[p.second];
            if(a[p.second] == a[l]){
                  s.erase({sz[l], l});
                  u_s(l, p.second);
            }
            if(a[f_s(p.second)] == a[r]){
                  s.erase({sz[r], r});
                  u_s(p.second, r);
            }
            if(sz[f_s(p.second)] != presz){
                  s.insert({sz[f_s(p.second)], f_s(p.second)});

            }
      }

      for(int i = 1; i <= n; i ++){
            a[i] = a[f_s(i)];
      }

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

Compilation message

route.cpp:32:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
route.cpp: In function 'int main()':
route.cpp:33:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%lld %lld", &n, &k);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~
route.cpp:36:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%lld", a + i);
             ~~~~~^~~~~~~~~~~~~~~

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	488 KB	Output is correct
3	Correct	2 ms	564 KB	Output is correct
4	Correct	2 ms	564 KB	Output is correct
5	Correct	2 ms	564 KB	Output is correct
6	Correct	2 ms	564 KB	Output is correct
7	Correct	2 ms	612 KB	Output is correct
8	Correct	2 ms	708 KB	Output is correct
9	Correct	2 ms	868 KB	Output is correct
10	Correct	45 ms	11016 KB	Output is correct
11	Correct	47 ms	11964 KB	Output is correct
12	Correct	31 ms	11964 KB	Output is correct
13	Runtime error	322 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
14	Halted	0 ms	0 KB	-