제출 #673640

#제출 시각아이디문제언어결과실행 시간메모리
673640Quan2003수열 (APIO14_sequence)C++17
60 / 100
61 ms131072 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int sz=1e5+10; const int mod = 1e9 + 7; int n,k,m,q,dis,lim; ll timer=1; long long sf[sz]; long long pf[sz]; long long dp[sz][2]; long long a[sz]; vector <long long>M; vector <long long>B; vector <long long>C; pair<int,int>par[sz][201]; bool bad(int l1,int l2,int l3) { return (B[l3]-B[l1])*(M[l1]-M[l2]) >= (B[l2]-B[l1])*(M[l1]-M[l3]); } void add(long long m,long long b, long long t) { C.push_back(t); M.push_back(m); B.push_back(b); while (M.size()>=3&&bad(M.size()-3,M.size()-2,M.size()-1)) { M.erase(M.end()-2); B.erase(B.end()-2); C.erase(C.end()-2); } } int pointer; pair<long long,int>query(long long x) { if(M.size() == 0) return {0,0}; if (pointer >=M.size()) pointer=M.size()-1; while (pointer<M.size()-1&& M[pointer+1]*x+B[pointer+1]>M[pointer]*x+B[pointer]) pointer++; return {M[pointer]*x+B[pointer],C[pointer]}; } int main(){ scanf("%d%d",&n,&k); for(int i = 1; i <= n; i++) scanf("%d",a + i); for(int i = 1; i <= n; i++) pf[i] = pf[i - 1] + a[i]; for(int i = n; i > 0 ; i--) sf[i] = sf[i + 1] + a[i]; for(int j = 1; j <= k; j++){ M.clear(); B.clear(); C.clear(); for(int i = 0; i <= n; i++){ pair<long long,int>opt = query(sf[i + 1]); dp[i][1] = opt.first + pf[i]*sf[i + 1]; add(-pf[i], dp[i][0], i); par[i][j] = {opt.second,j - 1}; } for(int i = 1; i <= n; i++) dp[i][0] = dp[i][1]; } long long ans = - LLONG_MAX; int pos = 0; for(int i = 1; i <= n; i++){ if(ans < dp[i][1]){ ans = dp[i][1]; pos = i; } } cout<<ans<<endl; int move = k; vector<int>res; while(move > 0 and pos > 0){ res.push_back(pos); pair<int,int>opt = par[pos][move]; pos = opt.first; move = opt.second; } reverse(res.begin(),res.end()); for(int i = 0; i < res.size(); i++) cout<<res[i]<< ' '; cout<<endl; }

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

sequence.cpp: In function 'std::pair<long long int, int> query(long long int)':
sequence.cpp:36:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         if (pointer >=M.size())
      |             ~~~~~~~~^~~~~~~~~~
sequence.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         while (pointer<M.size()-1&&
      |                ~~~~~~~^~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:45:43: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   45 |       for(int i = 1; i <= n; i++) scanf("%d",a + i);
      |                                          ~^  ~~~~~
      |                                           |    |
      |                                           int* long long int*
      |                                          %lld
sequence.cpp:76:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |       for(int i = 0; i < res.size(); i++) cout<<res[i]<< ' ';
      |                      ~~^~~~~~~~~~~~
sequence.cpp:44:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |       scanf("%d%d",&n,&k);
      |       ~~~~~^~~~~~~~~~~~~~
sequence.cpp:45:40: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |       for(int i = 1; i <= n; i++) scanf("%d",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...