제출 #90294

#제출 시각아이디문제언어결과실행 시간메모리
90294mirbek01등산 경로 (IZhO12_route)C++17
0 / 100
2 ms448 KiB
# include <bits/stdc++.h> using namespace std; const int N = 1e6 + 2; int n, k, a[N], p[N], sz[N], L[N], R[N]; long long bg = 0, cur = 0; 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]; a[y] = max(a[x], a[y]); } } int main(){ scanf("%d %d", &n, &k); for(int i = 1; i <= n; i ++){ scanf("%d", 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){ if(a[1] < a[2]){ a[1] += k; a[1] = min(a[2], a[1]); cout << abs(a[1] - a[2]) * 2 << endl; } else { a[2] += k; a[2] = min(a[2], a[1]); cout << abs(a[1] - a[2]) * 2 << 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, R[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(R[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]){ u_s(l, p.second); } if(a[f_s(p.second)] == a[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; }

컴파일 시 표준 에러 (stderr) 메시지

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("%d %d", &n, &k);
       ~~~~~^~~~~~~~~~~~~~~~~
route.cpp:36:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", a + i);
             ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...