제출 #1023539

#제출 시각아이디문제언어결과실행 시간메모리
1023539daffuwu수열 (APIO14_sequence)C++14
62 / 100
531 ms84428 KiB
#include <bits/stdc++.h> using namespace std; #define fr first #define sc second mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); int n, k, opt[100002][202], ps[100069]; long long dp[100069][2]; struct line { int m; long long c; int id; long long f(int x) { return 1ll*m*x+c; } double intersect(line oth) { return 1.0*(c-oth.c)/(oth.m-m); } } cur; vector<line> vc; int main() { int i, j, ii, c; scanf("%d%d", &n, &k); k++; for (i=1; i<=n; i++) { scanf("%d", ps+i); ps[i] += ps[i-1]; } for (c=2; c<=k; c++) { for (i=c, j=0; i<=n; i++) { vc.push_back({ps[i-1], dp[i-1][(c+1)%2]-1ll*ps[i-1]*ps[i-1], i-1}); for (; j+1<vc.size() && vc[j].f(ps[i])<=vc[j+1].f(ps[i]); j++); j = min(j, (int)vc.size()-1); dp[i][c%2] = vc[j].f(ps[i]); opt[i][c] = vc[j].id; cur = {ps[i], dp[i][(c+1)%2]-1ll*ps[i]*ps[i], i}; for (; vc.size()>=2 && vc[vc.size()-2].intersect(vc.back())>=vc.back().intersect(cur); vc.pop_back()); } vc.clear(); } printf("%lld\n", dp[n][k%2]); for (i=n, c=k; c>=2; i=opt[i][c], c--) { printf("%d ", opt[i][c]); } printf("\n"); }

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

sequence.cpp: In function 'int main()':
sequence.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |             for (; j+1<vc.size() && vc[j].f(ps[i])<=vc[j+1].f(ps[i]); j++);
      |                    ~~~^~~~~~~~~~
sequence.cpp:28:15: warning: unused variable 'ii' [-Wunused-variable]
   28 |     int i, j, ii, c;
      |               ^~
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, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~
sequence.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         scanf("%d", ps+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...