제출 #106918

#제출 시각아이디문제언어결과실행 시간메모리
106918nxteru수열 (APIO14_sequence)C++14
100 / 100
542 ms83704 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef double D; typedef pair<ll,ll> P; #define M 1000000007 #define F first #define S second #define PB push_back #define INF 1000000000000000000 struct t{ ll x,y,q; }; bool check(t a,t b,t c){ return (c.y-b.y)*(a.x-b.x)<=(b.y-a.y)*(b.x-c.x); } int n,m,b[205][100005],l,r; ll dp[2][100005],s[100005]; t dq[100005]; vector<int>ans; int main(void){ scanf("%d%d",&n,&m); m++; for(int i=1;i<=n;i++){ ll a; scanf("%d",&a); s[i]=s[i-1]+a; } for(int j=0;j<=n;j++)dp[0][j]=INF; dp[0][0]=0; for(int i=1;i<=m;i++){ l=0,r=0; int o=(i-1)%2,p=i%2; for(int j=0;j<=n;j++)dp[p][j]=INF; for(int j=1;j<=n;j++){ if(dp[o][j-1]<INF){ t p=t{-2LL*s[j-1],s[j-1]*s[j-1]+dp[o][j-1],j-1}; while(r-2>=l&&check(dq[r-2],dq[r-1],p))r--; dq[r++]=p; while(l+1<r&&dq[l].x*s[j]+dq[l].y>=dq[l+1].x*s[j]+dq[l+1].y)l++; } if(l<r){ b[i][j]=dq[l].q; dp[p][j]=dq[l].x*s[j]+dq[l].y+s[j]*s[j]; } } } printf("%lld\n",(s[n]*s[n]-dp[m%2][n])/2LL); int x=n; for(int i=m;i>1;i--){ ans.PB(b[i][x]); x=b[i][x]; } for(int i=ans.size()-1;i>=0;i--){ printf("%d",ans[i]); if(i==0)printf("\n"); else printf(" "); } }

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

sequence.cpp: In function 'int main()':
sequence.cpp:26:16: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll* {aka long long int*}' [-Wformat=]
   scanf("%d",&a);
              ~~^
sequence.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
sequence.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a);
   ~~~~~^~~~~~~~~
#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...