제출 #23465

#제출 시각아이디문제언어결과실행 시간메모리
23465rubabredwan수열 (APIO14_sequence)C++14
0 / 100
53 ms93512 KiB
/* Bismillahir Rahmanir Rahim */ #include <bits/stdc++.h> using namespace std; const int N = 100005; const int K = 205; vector<long long>M, B, id; int ptr; bool bad(int a, int b, int c){ return (B[a] - B[b]) * (M[c] - M[a]) >= (B[a] - B[c]) * (M[b] - M[a]); } void add(long long m, long long b, int i){ M.push_back(m); B.push_back(b); id.push_back(i); while(M.size() >= 3 && bad(M.size()-3, M.size()-2, M.size()-1)){ M.erase(M.end()-2); B.erase(B.end()-2); } } long long query(long long x){ if(ptr >= M.size()) ptr = M.size() - 1; while(ptr + 1 < M.size() && M[ptr+1] * x + B[ptr+1] > M[ptr] * x + B[ptr]){ ++ptr; } assert(ptr >= 0 && ptr < M.size()); return M[ptr] * x + B[ptr]; } long long cur[N], past[N]; int fk[N][K]; long long A[N], sum[N]; int n, k; int main(){ scanf("%d %d", &n, &k); for(int i=1;i<=n;i++){ scanf("%lld", &A[i]); sum[i] = sum[i-1] + A[i]; } for(int j=1;j<=k;j++){ M.clear(); B.clear(); ptr = 0; add(sum[1], -(sum[1] * sum[1]), 1); for(int i=2;i<=n;i++){ cur[i] = query(sum[i]); fk[i][j] = id[ptr]; add(sum[i], -(sum[i] * sum[i]) + past[i], i); } for(int i=1;i<=n;i++) past[i] = cur[i]; } cout << cur[n] << endl; while(k){ cout << fk[n][k] << ' '; n = fk[n][k]; k = k - 1; } cout << endl; return 0; }

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

sequence.cpp: In function 'long long int query(long long int)':
sequence.cpp:28:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(ptr >= M.size()) ptr = M.size() - 1;
            ^
sequence.cpp:29:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ptr + 1 < M.size() && M[ptr+1] * x + B[ptr+1] > M[ptr] * x + B[ptr]){
                   ^
In file included from /usr/include/c++/5/cassert:43:0,
                 from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:33,
                 from sequence.cpp:3:
sequence.cpp:32:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     assert(ptr >= 0 && ptr < M.size());
                            ^
sequence.cpp: In function 'int main()':
sequence.cpp:42:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &k);
                           ^
sequence.cpp:44:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &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...