답안 #90324

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

route

# include <bits/stdc++.h>

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){
      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];
      }
}

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;
            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 = L[p.second] - 1, r = p.second + 1;
            if(l < 1)
                  l = n;
            if(r > n)
                  r = 1;
            l = f_s(l);
            r = f_s(r);
            if(a[l] <= a[p.second] || a[r] <= a[p.second])
                  continue;
            while(!sz[p.second]){

            }
            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: In function 'int main()':
route.cpp:25: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:28:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", a + i);
             ~~~~~^~~~~~~~~~~~~

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	448 KB	Output is correct
4	Correct	2 ms	592 KB	Output is correct
5	Correct	2 ms	628 KB	Output is correct
6	Correct	2 ms	628 KB	Output is correct
7	Correct	2 ms	628 KB	Output is correct
8	Correct	2 ms	628 KB	Output is correct
9	Correct	2 ms	628 KB	Output is correct
10	Correct	37 ms	6864 KB	Output is correct
11	Correct	44 ms	6864 KB	Output is correct
12	Correct	28 ms	6864 KB	Output is correct
13	Correct	464 ms	63688 KB	Output is correct
14	Runtime error	473 ms	66560 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
15	Halted	0 ms	0 KB	-