글 읽기 - 풀이보다 시간차이에 대해서 궁금합니다.

chpark1111 4년 전 1

이 두 코드는 완전히 같은 코드인데도 불구하고 왜 시간차이가 1초나 나죠...?

또 다시 넣어보면 또 시간이 달라집니다... 왜그렇죠???

시간체크하는 방법이 궁금합니다!

https://www.acmicpc.net/source/15342101

https://www.acmicpc.net/source/15342156

아래는 시간차이가 생긴 소스입니다..

혹시 시간을 조금이라도 줄일 방법이 있는지도 궁금합니다!!..

#include <bits/stdc++.h>
#define f first
#define s second
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> pi;
 
ll cnt,sz,n,k,p[100006],dp[100002][5];
int sv[100002][202],st[100005],v[100006];
vector<int> anw;
 
double get(ll a,ll b,ll q)
{
	a=st[a],b=st[b];
	ll pb=p[b],pa=p[a];
	if(pa==pb) return -1e15;
	return (double)(pb*pb-pa*pa+dp[a][q%2]-dp[b][q%2])/(double)(pb-pa);
}
 
void push(ll x,ll d)
{
	st[sz]=x;
	while(sz>=2&&get(sz,sz-1,d)<get(sz-1,sz-2,d))
		sz--,st[sz]=x;
	sz++;
}
 
ll val(ll x,ll d)
{
	while(cnt<sz-1&&p[x]>=get(cnt,cnt+1,d)) cnt++;
	ll nw=st[cnt];sv[x][d+1]=nw;
	return p[x]*p[nw]-p[nw]*p[nw]+dp[nw][d%2];
}
 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>v[i],p[i]=p[i-1]+(ll)v[i];
	for(int i=1;i<=k;i++)
	{
		cnt=0,sz=0;
		push(0,0);
		for(int j=1;j<=n;j++)
		{
			dp[j][i%2]=val(j,i-1);
			push(j,i-1);
		}
	}
	cout<<dp[n][k%2]<<"\n";
	ll g=n;
	for(int i=k;i>=1;i--)
	{
		g=sv[g][i];
		anw.push_back(g);
	}
	reverse(anw.begin(),anw.end());
	for(int i=0;i<k;i++)
		cout<<anw[i]<<" ";
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

풀이보다 시간차이에 대해서 궁금합니다.

chpark1111 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말