이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define setbit(s, i) (s|=(1LL<<(i)))
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
typedef long long ll;
typedef long double ld;
template <typename T> inline void read(T &x){
cin>>x;
// scanf("%lld", &x);
// char c;
// bool nega=0;
// while((!isdigit(c=getchar()))&&(c!='-'));
// if(c=='-'){
// nega=1;
// c=getchar();
// }
// x=c-48;
// while(isdigit(c=getchar())) x=x*10+c-48;
// if(nega) x=-x;
}
template <typename T> inline void writep(T x){
if(x>9) writep(x/10);
putchar(x%10+48);
}
template <typename T> inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
writep(x);
}
template <typename T> inline void writeln(T x){
write(x);
putchar('\n');
}
#define taskname "sequence"
#define sqr(x) ((x)*(x))
int n, k;
int s[100001];
ll sqs[100001];
ll f[100001];
int trace[100001][201];
vector <int> q;
const ll inf=mask(60);
void track(int nn, int k){
if(nn==0) return;
track(trace[nn][k], k-1);
if(nn==n) return;
write(nn);
putchar(' ');
}
int first[100001];
ll b[100001];
ll first_better(int i, int j){
if(b[j]<=b[i]) return 0;
if(s[i]==s[j]) return inf;
return (b[j]-b[i]-1)/(s[i]-s[j])+1;
}
int main(){
#ifdef Kanikou
if(fopen(taskname".inp", "r"))
freopen(taskname".inp", "r", stdin);
#endif // Kanikou
ios_base::sync_with_stdio(false);
cin.tie(NULL);
read(n);
read(k);
FOR(i, 1, n) read(s[i]);
FOR(i, 1, n) s[i]+=s[i-1];
FOR(i, 1, n) sqs[i]=((ll)s[i])*s[i];
ll a;
FOR(j, 1, k){
int p=0;
q.clear();
q.pb(0);
FOR(i, 1, n){
b[i]=f[i]-sqs[i];
p=min(p, ((int)q.size())-1);
while((p+1<q.size())&&(first[q[p+1]]<=s[i])) p++;
f[i]=((ll)s[i])*s[q[p]]+b[q[p]];
trace[i][j]=q[p];
while(true){
a=first_better(i, q.back());
if(a>=s[n]) break;
if(a<=first[q.back()]){
q.pop_back();
if(q.empty()){
first[i]=0;
q.pb(i);
break;
}
}
else{
first[i]=a;
q.pb(i);
break;
}
}
}
}
writeln(f[n]);
track(n, k);
}
컴파일 시 표준 에러 (stderr) 메시지
sequence.cpp: In function 'int main()':
sequence.cpp:87:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while((p+1<q.size())&&(first[q[p+1]]<=s[i])) p++;
~~~^~~~~~~~~
# | 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... |