제출 #538673

#제출 시각아이디문제언어결과실행 시간메모리
538673nicholask수열 (APIO14_sequence)C++14
0 / 100
64 ms131072 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int dp[100001][201]; int bac[100001][201]; signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n,k; cin>>n>>k; k++; int a[n+1]; for (int i=1; i<=n; i++) cin>>a[i]; int ps[n+1]={}; for (int i=1; i<=n; i++) ps[i]=ps[i-1]+a[i]; for (int j=1; j<=k; j++){ deque <int> q; q.push_back(0); for (int i=1; i<=n; i++){ while (q.size()>=2&&dp[q[1]][j-1]-dp[q[0]][j-1]>(ps[n]-ps[i])*(ps[q[1]]-ps[q[0]])) q.pop_front(); dp[i][j]=dp[q[0]][j-1]+(ps[i]-ps[q[0]])*(ps[n]-ps[i]); bac[i][j]=q[0]; while (q.size()>=2&&(dp[q.back()][j-1]-dp[q[q.size()-2]][j-1])*(ps[i]-ps[q.back()])<(dp[i][j-1]-dp[q.back()][j-1])*(ps[q.back()]-ps[q[q.size()-2]])) q.pop_back(); q.push_back(i); } } cout<<dp[n][k]<<'\n'; vector <int> v; v.push_back(n); for (int i=k; i>1; i--) v.push_back(bac[v.back()][i]); reverse(v.begin(),v.end()); for (int i=0; i+1<v.size(); i++) cout<<v[i]<<" \n"[i+2==v.size()]; }

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

sequence.cpp: In function 'int main()':
sequence.cpp:31:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int i=0; i+1<v.size(); i++) cout<<v[i]<<" \n"[i+2==v.size()];
      |                   ~~~^~~~~~~~~
sequence.cpp:31:59: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int i=0; i+1<v.size(); i++) cout<<v[i]<<" \n"[i+2==v.size()];
      |                                                        ~~~^~~~~~~~~~
#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...