제출 #23154

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
23154		ngkan146	수열 (APIO14_sequence)	C++98	0 / 100	0 ms	1848 KiB

sequence

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,k,a[100005];
ll dp[100005][205];
int last[100005][205];
vector <ll> M,B,ID;
bool check(int id){
   return (B[id] - B[id-2]) * (M[id-2] - M[id-1]) <= (B[id-1] - B[id-2]) * (M[id-2] - M[id]);
}
void add_line(ll slope,ll val,ll id){
   M.push_back(slope);
   B.push_back(val);
   ID.push_back(id);
   while(M.size() >= 3 && check(M.size()-1)) ID.erase(ID.end()-2), M.erase(M.end()-2), B.erase(B.end()-2);
}
int ctrl;
ll get(ll x){
   ctrl = min(ctrl, (int)M.size()-1);
   while(ctrl < M.size()-1 && M[ctrl] * x + B[ctrl] < M[ctrl+1] * x + B[ctrl+1])
      ++ctrl;
   return ID[ctrl];
}
int main(){
   scanf("%d %d",&n,&k);
   for(int i=1;i<=n;i++)
      scanf("%d",&a[i]),
      a[i] += a[i-1];
   for(int t=1;t<=k;t++){
      M.clear(); B.clear(); ID.clear();
      add_line(0,0,0);
      for(int i=1;i<=n;i++){
         int id = get(a[i]);
         dp[i][t] = M[id] * a[i] + B[id];
         last[i][t] = id;
         add_line(a[i], dp[i][t-1] - a[i] * a[i], i);
      }
   }
   vector <int> res;
   int mjk = n;
   for(int t=k;t>=1;t--){
      res.push_back(last[mjk][t]);
      mjk = last[mjk][t];
   }
   reverse(res.begin(),res.end());
   printf("%lld\n",dp[n][k]);
   for(int i=0;i<res.size();i++) printf("%d ",res[i]);
}
/*
7 3
4 1 3 4 0 2 3
*/

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

sequence.cpp: In function 'long long int get(long long int)':
sequence.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(ctrl < M.size()-1 && M[ctrl] * x + B[ctrl] < M[ctrl+1] * x + B[ctrl+1])
               ^
sequence.cpp: In function 'int main()':
sequence.cpp:47:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<res.size();i++) printf("%d ",res[i]);
                 ^
sequence.cpp:25:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d",&n,&k);
                        ^
sequence.cpp:28:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       a[i] += a[i-1];
                     ^

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29