이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <cstdio>
#include <vector>
#include <utility>
#include <tuple>
#include <cassert>
#define F first
#define S second
#define SZ(x) ((int)x.size())
using namespace std;
template<class T>
struct CHT {
using pt = pair<T,T>;
vector<pt> ln;
vector<int> idx;
int curr = 0;
bool bad(pt& a, pt& b, T x) {
return (b.S - a.S) >= x * (a.F - b.F);
}
bool bad(pt& a, pt& b, pt& c) {
return (b.S - a.S) * (b.F - c.F) >= (c.S - b.S) * (a.F - b.F);
}
void insert(pt v, int i) {
if(SZ(ln) > 0 && ln.back().F == v.F) {
if(ln.back().S > v.S) return;
else ln.pop_back(), idx.pop_back();
}
while(SZ(ln) >= 2 && bad(ln[SZ(ln)-2], ln.back(), v))
ln.pop_back(), idx.pop_back();
ln.push_back(v), idx.push_back(i);
}
pair<T, int> query(T x) {
assert(SZ(ln) > 0);
curr = min(curr, SZ(ln) - 1);
while(curr < SZ(ln) - 1 && bad(ln[curr], ln[curr+1], x))
curr++;
return {x * ln[curr].F + ln[curr].S, idx[curr]};
}
void clear() {
ln.clear();
idx.clear();
curr = 0;
}
};
int n, k, rec[100010][202];
long long s[100010], dp[100010], currDP;
CHT<long long> cht;
int main() {
scanf("%d%d", &n, &k);
for(int i=1; i<=n; i++) scanf("%lld", s+i), s[i] += s[i-1];
for(int j=2; j<=k+1; j++) {
cht.clear();
cht.insert({s[j-1], dp[j-1] - s[j-1]*s[j-1]}, j-1);
for(int i=j; i<=n; i++) {
tie(currDP, rec[i][j]) = cht.query(s[i]);
cht.insert({s[i], dp[i] - s[i]*s[i]}, i);
dp[i] = currDP;
}
}
long long ans = 0;
//printf("%lld\n", dp[n]);
int p = n;
vector<int> res;
while(k > 0) {
res.push_back(rec[p][k+1]);
p = rec[p][k+1], k--;
}
for(int i=SZ(res)-1; i>=0; i--)
ans += (s[res[i]] - (i<SZ(res)-1 ? s[res[i+1]] : 0)) * (s[n] - s[res[i]]);
printf("%lld\n", ans);
for(int i=SZ(res)-1; i>=0; i--) printf("%d ", res[i]);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
sequence.cpp: In function 'int main()':
sequence.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &k);
~~~~~^~~~~~~~~~~~~~~~
sequence.cpp:49:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1; i<=n; i++) scanf("%lld", s+i), s[i] += s[i-1];
~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |