제출 #426250

#제출 시각아이디문제언어결과실행 시간메모리
426250zoooma13수열 (APIO14_sequence)C++14
0 / 100
22 ms4084 KiB
#include <bits/stdc++.h> using namespace std; int64_t sqr(int x){ return 1LL*x*x; } struct line{ int64_t m ,c; int idx; int64_t eval(int64_t x) { return m*x + c; } }; struct hull : deque <line> { void add(int64_t m ,int64_t c ,int idx){ line l = {m ,c ,idx}; while(size() >= 2 && 1.0*(c - back().c)*(back().m - at(size()-2).m) <= 1.0*(back().m - m)*(at(size()-2).c - back().c)) pop_back(); push_back(l); } pair <int64_t ,int> eval(int64_t x){ while(size() >= 2 && at(0).eval(x) <= at(1).eval(x)) pop_front(); return {at(0).eval(x) , at(0).idx}; } }; int main() { int n ,m; scanf("%d%d",&n,&m); vector <int> a(n) ,s{0}; for(int&i : a){ scanf("%d",&i); s.push_back(s.back() + i); } vector <int64_t> dp(n+1) ,last_dp(n+1); vector <vector <int>> trace(1 ,vector <int> (n+1 ,0)); for(int i = 0; i <= n; i++) dp[i] = sqr(s[i]); for(int k = 1; k <= m; k++){ last_dp = dp; trace.push_back(vector <int> (n+1 ,0)); auto&from = trace.back(); hull h; h.add(s[k] ,-sqr(s[k])-last_dp[k] ,k); for(int i = k+1; i <= n; i++){ auto r = h.eval(2*s[i]); dp[i] = sqr(s[i]) - r.first; from[i] = r.second; h.add(s[i] ,-sqr(s[i])-last_dp[i] ,i); } } printf("%lld\n",(sqr(s.back()) - dp.back()) / 2); for(int l = m ,i = n; l > 0; l--){ i = trace[l][i]; printf("%d ",i); } printf("\n"); }

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

sequence.cpp: In function 'int main()':
sequence.cpp:54:16: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int64_t' {aka 'long int'} [-Wformat=]
   54 |     printf("%lld\n",(sqr(s.back()) - dp.back()) / 2);
      |             ~~~^    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      |                |                                |
      |                long long int                    int64_t {aka long int}
      |             %ld
sequence.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
sequence.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         scanf("%d",&i);
      |         ~~~~~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...