답안 #90322

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
90322	2018-12-21T08:46:33 Z	mirbek01	등산 경로 (IZhO12_route)	C++17	0 / 100	466 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){
      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];
      }
}

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 = f_s(L[p.second] - 1), r = f_s(p.second + 1);
            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:31: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:34: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	380 KB	Output is correct
3	Correct	2 ms	584 KB	Output is correct
4	Correct	2 ms	584 KB	Output is correct
5	Correct	2 ms	584 KB	Output is correct
6	Correct	2 ms	584 KB	Output is correct
7	Correct	2 ms	584 KB	Output is correct
8	Correct	2 ms	584 KB	Output is correct
9	Correct	2 ms	584 KB	Output is correct
10	Correct	40 ms	6788 KB	Output is correct
11	Correct	44 ms	6788 KB	Output is correct
12	Correct	29 ms	6788 KB	Output is correct
13	Runtime error	466 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.
14	Halted	0 ms	0 KB	-