제출 #338873

#제출 시각아이디문제언어결과실행 시간메모리
338873beksultan04등산 경로 (IZhO12_route)C++14
0 / 100
54 ms65540 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]; } } deque <int> v[100000]; main(){ int i,j,k,ans=0,asd=0; scan2(n,k) for (i=1;i<=n;++i){ scan1(q[i]) } q[n+1]=q[1]; for (i=1;i<=n;++i){ ans+=abs(q[i+1]-q[i]); } int l=1,r=INF; 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]; vector <int> may; int c=0; for (i=1;i<=n;++i){ if (q[i] == asd){ c++; } else if(c){ if (c < 100000){ v[c].pb(i); if (used[c] == 0) may.pb(c); used[c]=1; } c=0; } } sort(all(may)); for (c = 0;c<may.size();++c){ int x = may[c]; while (!v[x].empty() && x <= k){ int l = v[x][0]-x; int r = v[x][0]-1; v[x].pop_front(); int mn = min(abs(q[l-1]-q[l]),abs(q[r+1]-q[r])); while (mn*x > k)mn--; k-=mn*x; for (j =l;j<=r;++j)q[j]+=mn; } } 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:40:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |         int m = l+r>>1;
      |                 ~^~
route.cpp:74:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for (c = 0;c<may.size();++c){
      |                ~^~~~~~~~~~~
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...