제출 #338876

#제출 시각아이디문제언어결과실행 시간메모리
338876beksultan04등산 경로 (IZhO12_route)C++14
0 / 100
16 ms23808 KiB
#include <bits/stdc++.h> using namespace std; //#define int long long #define pii pair<int,int> #define OK puts("OK"); #define NO puts("NO"); #define YES puts("YES"); #define fr first #define sc second #define ret return #define scan1(a) scanf("%d",&a); #define scan2(a,b) scanf("%d %d",&a, &b); #define scan3(a,b,c) scanf("%d %d %d",&a,&b,&c); #define all(s) s.begin(),s.end() #define allr(s) s.rbegin(),s.rend() #define pb push_back #define sz(v) (int)v.size() #define endi puts(""); const int N = 1e6+12,INF=1e9+7; int q[N],n; bool used[N]; inline void fun(int x,int &ans){ for (int i=1;i<=n;++i){ if (q[i] < x)ans+=x-q[i]; } } vector <int> v[N]; main(){ int i,j,k,ans=0,mx=0,asd=0; scan2(n,k) for (i=1;i<=n;++i){ scan1(q[i]) mx=max(mx,q[i]); } q[n+1]=q[1]; for (i=1;i<=n;++i){ ans+=abs(q[i+1]-q[i]); } int l=1,r=mx; while (r-l>1){ int m = l+r>>1; int x = 0; fun(m,x); if (x >= k)r=m; else l=m; } int x = 0; fun(r,x); if (x <= k)l=r; for (i=1;i<=n;++i){ if (q[i] < l){ k-=l-q[i]; q[i] = l; } } asd=l; q[n+1]=q[1]; set <int> may; int c=0; for (i=1;i<=n;++i){ if (q[i] == asd){ c++; } else if(c){ v[c].pb(i); if (used[c] == 0) may.insert(c); used[c]=1; c=0; } } while (!may.empty()){ int x = *may.begin(); may.erase(may.begin()); while (!v[x].empty() && x <= k){ int to = v[x].size()-1; int l = v[x][to]-x; int r = v[x][to]-1; v[x].pop_back(); int mn = min(abs(q[l-1]-q[l]),abs(q[r+1]-q[r])); while (mn*x > k && mn > 0)mn--; k -= mn*x; for (j=l;j<=r;++j)q[j]+=mn; if (q[r] == q[r+1]) v[x+1].pb(r+2); else v[x+1].pb(r+1); may.insert(x+1); } } q[n+1]=q[1]; int y =0; for (i=1;i<=n;++i){ y+=abs(q[i+1]-q[i]); } cout <<ans-y; }

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

route.cpp:28:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   28 | main(){
      |      ^
route.cpp: In function 'int main()':
route.cpp:41:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |         int m = l+r>>1;
      |                 ~^~
route.cpp:12:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   12 | #define scan2(a,b) scanf("%d %d",&a, &b);
      |                    ~~~~~^~~~~~~~~~~~~~~~
route.cpp:30:5: note: in expansion of macro 'scan2'
   30 |     scan2(n,k)
      |     ^~~~~
route.cpp:11:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   11 | #define scan1(a) scanf("%d",&a);
      |                  ~~~~~^~~~~~~~~
route.cpp:32:9: note: in expansion of macro 'scan1'
   32 |         scan1(q[i])
      |         ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...