제출 #673653

#제출 시각아이디문제언어결과실행 시간메모리
673653Quan2003수열 (APIO14_sequence)C++17
60 / 100
64 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 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,-INT_MAX}; 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 j = 1; j <= k; j++){ M.clear(); B.clear(); C.clear(); for(int i = 0; i < n; i++){ pair<long long,int>opt = query(pf[n] - pf[i]); dp[i][1] = opt.first + pf[i]*(pf[n] - pf[i]); 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; } } int move = k; vector<int>res; while(pos > 0){ res.push_back(pos); pair<int,int>opt = par[pos][move]; pos = opt.first; move = opt.second; } reverse(res.begin(),res.end()); cout << ans << '\n'; for(int i = 0; i < res.size(); i++) { cout << res[i] << ' '; } cout << '\n'; }

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

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