제출 #241053

#제출 시각아이디문제언어결과실행 시간메모리
241053Nicholas_Patrick수열 (APIO14_sequence)C++17
100 / 100
1630 ms81776 KiB
#include <cstdio> #include <queue> #include <algorithm> using namespace std; int n, k; vector <long long> a; vector <long long> memo1, memo2; vector <vector <int> > opt; int i; void solven(int l=1, int r=n, int ll=1, int rr=n){//[], [] if(l>r) return; long long best=-1; int mid=(l+r)/2; long long&ret=memo2[mid]; int&optt=opt[i][mid]; optt=-1; ret=-1ll; for(int i = ll;i <= min(mid, rr);i ++){ if(ret<(a[mid]-a[i])*(a[i]-a[0])+memo1[i]){ optt=i; ret=(a[mid]-a[i])*(a[i]-a[0])+memo1[i]; } } solven(l, mid-1, ll, optt); solven(mid+1, r, optt, rr); } long long solvenk(){ opt.resize(k+1, vector <int> (n+1)); memo1.assign(n+1, 0); memo2.assign(n+1, 0); for(i = 1;i <= k;i ++){ solven(); swap(memo1, memo2); } return memo1[n]; } int main(){ scanf("%d%d", &n, &k); a.resize(n+1); a[0]=0ll; for(i = 1;i <= n;i ++){ scanf("%lld", &a[i]); a[i]+=a[i-1]; } printf("%lld\n", solvenk()); int j = n; vector <int> ans; for(i = k;i;i --){ ans.push_back(opt[i][j]); j=opt[i][j]; } sort(ans.begin(), ans.end()); for(int i = 1;i < k;i ++){ while(ans[i-1]>=ans[i]){ ans[i]++; } } for(int i = 0;i < k;i ++){ printf("%d%c", ans[i], i==k-1?'\n':' '); } }

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

sequence.cpp: In function 'void solven(int, int, int, int)':
sequence.cpp:14:12: warning: unused variable 'best' [-Wunused-variable]
  long long best=-1;
            ^~~~
sequence.cpp: In function 'int main()':
sequence.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~
sequence.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &a[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...