oj.uz

답안 #197472

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
197472 2020-01-21T12:12:28 Z red1108 수열 (APIO14_sequence) C++17
0 / 100
 121 ms 84892 KB 
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false);cin.tie(0)
#define eb emplace_back
typedef long long ll;
typedef pair<ll,ll> pll;
struct A{
	ll a, b;
	int ind;
	A(){}
	A(ll x, ll y, int z){a=x;b=y;ind=z;}
};
struct CHT{
	int top = 0;
	vector<A> line;
	void clear(){
		top = 0;
		line.clear();
	}
	double cross(A a, A b){
		return (double)(b.b-a.b)/(double)(a.a-b.a);
	}
	void add(A l){
		while(line.size()>1&&cross(line[line.size()-2], line.back())>=cross(line.back(), l)) line.pop_back();
		line.eb(l);
	}
	pll get(ll x){
		top = min(top, (int)line.size()-1);
		while(top+1<line.size()&&cross(line[top], line[top+1])<=x) top++;
		return pll(line[top].a * x + line[top].b, line[top].ind);
	}
}cht, nxt;
ll s[100010];
int bac[100010][201];
int n, k;
vector<int> h;
int main(){
	fastio;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		int a;cin>>a;
		s[i]=s[i-1]+a;
	}
	cht.add(A(0,0,0));
	ll ans=0;
	for(int i=0;i<=k;i++){
		for(int j=1;j<=n;j++){
			pll g = cht.get(s[j]);
			nxt.add(A(s[j], g.fi-s[j]*s[j],j));
			bac[j][i] = g.se;
			if(j==n&&i==k) ans = g.fi;
		}
		cht = nxt;
		nxt.clear();
	}
	cout<<ans<<endl;
	while(n){
		n = bac[n][k];
		k--;
		h.eb(n);
	}
	reverse(h.begin(), h.end());
	for(int i=1;i<h.size();i++) cout<<h[i]<<" ";
}

Compilation message

sequence.cpp: In member function 'pll CHT::get(ll)':
sequence.cpp:31:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(top+1<line.size()&&cross(line[top], line[top+1])<=x) top++;
         ~~~~~^~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:65:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<h.size();i++) cout<<h[i]<<" ";
              ~^~~~~~~~~

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB contestant found the optimal answer: 108 == 108
2 Correct 2 ms 376 KB contestant found the optimal answer: 999 == 999
3 Incorrect 2 ms 376 KB Integer 2 violates the range [1, 1]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB contestant didn't find the optimal answer: 252308 < 1093956
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 504 KB position 2 occurs twice in split scheme
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 1144 KB position 2 occurs twice in split scheme
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 8948 KB contestant didn't find the optimal answer: 1187850 < 1818678304
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 121 ms 84892 KB contestant didn't find the optimal answer: 5054352 < 19795776960
2 Halted 0 ms 0 KB -