제출 #226291

#제출 시각아이디문제언어결과실행 시간메모리
226291bharat2002수열 (APIO14_sequence)C++14
0 / 100
2091 ms384 KiB
/*input 7 3 4 1 3 4 0 2 3 */ #include<bits/stdc++.h> using namespace std; const int N=1e5 + 100; const int mod=1e9 + 7; #define int long long const int inf=1e18; #define pii pair<int, int> #define f first #define s second #define mp make_pair #define FOR(i, n) for(int i=1;i<=n;i++) #define TRACE(x) cerr << #x << " = " << x << endl //Trace prints the name of the variable and the value. int dp[N][210], arr[N], n, k, pref[N], p[N][210]; deque<int> st;int ind; void func(bool a) { while(true) {} } double inter(int a, int b) { func(a!=b); double ret=(dp[a][ind] - dp[b][ind] + 0.0)/(pref[a] - pref[b] + 0.0); return ret; } void remove() { while(st.size()>=3) { int i1=st.front(), i2, i3;st.pop_front();i2=st.front();st.pop_front();i3=st.front(); if(inter(i1, i3)<=inter(i2, i3)) st.push_front(i1); else {st.push_front(i2);st.push_front(i1);return;} } } signed main() { ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); cin>>n>>k;pref[0]=0; func(n<=1e5);func(k<=200); if(n==1) { cout<<0;return 0; } for(int i=1;i<=n;i++) {cin>>arr[i];pref[i]=arr[i] + pref[i-1];} for(int i=1;i<=n;i++) { for(int j=1;j<=k;j++) dp[i][j]=0; } for(int i=1;i<=n;i++) { dp[i][1]=pref[i]*(pref[n]-pref[i]); } for(int j=2;j<=k;j++) { st.push_front(j-1);ind=j-1; for(int i=j;i<=n;i++) { while(st.size()>1) { int a=st.front();st.pop_front();int b=st.front(); if(dp[a][ind] - pref[a]*(pref[n]-pref[i])>dp[b][ind]-pref[b]*(pref[n]-pref[i])) {st.push_front(a);break;} } int opt=st.front(); dp[i][j]=dp[opt][j-1] -pref[opt]*(pref[n]-pref[i]); dp[i][j]+=(pref[i])*(pref[n]-pref[i]);p[i][j]=opt; st.push_back(i);remove(); } while(!st.empty()) st.pop_front(); } int mi, mval=-inf; for(int j=1;j<=n;j++) { if(mval<dp[j][k]) { mi=j;mval=dp[j][k]; } } cout<<mval<<endl; stack<int> sti;sti.push(mi); while(sti.size()<k) { int cur=p[sti.top()][k-sti.size()+1];sti.push(cur); } while(!sti.empty()) {cout<<sti.top()<<" ";sti.pop();} }

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

sequence.cpp: In function 'int main()':
sequence.cpp:85:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(sti.size()<k)
        ~~~~~~~~~~^~
#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...