提交记录 10228


用户 题目 状态 得分 用时 内存 语言 代码长度
hjk1030 noi19a. 【NOI2019】回家路线 Accepted 100 36.074 ms 12128 KB C++ 2.23 KB
提交时间 评测时间
2019-08-25 20:04:38 2020-08-01 02:04:07
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int mod=998244353;
typedef long long ll;
inline int add(int a,int b)
{
	if((a+=b)>=mod)a-=mod;
	return a;
}
inline int dec(int a,int b)
{
	if((a-=b)<0)a+=mod;
	return a;
}
inline int mult(int a,int b)
{
	long long t=1ll*a*b;
	if(t>=mod)t%=mod;
	return t;
}
inline int power(int a,int b)
{
	int out=1;
	while(b)
	{
		if(b&1)out=mult(out,a);
		a=mult(a,a);
		b>>=1;
	}
	return out;
}
int n,m,A,B,C;
int s[200010],e[200010],p[200010],q[200010];
inline int f(int x)
{
	return A*x*x+B*x+C;
}
vector<int> R[1010];
vector<pair<int,ll> > tb[100010];
priority_queue<pair<int,ll>,vector<pair<int,ll> >,greater<pair<int,ll> > > Q[100010];
void insert(int pos,pair<int,ll> x)
{
	x.second+=A*x.first*x.first-B*x.first;
	while(tb[pos].size()>=2)
	{
		pair<int,ll> p1=tb[pos][tb[pos].size()-2],p2=tb[pos].back(),p3=x;
		if((p3.second-p1.second)*(p2.first-p1.first)<=(p2.second-p1.second)*(p3.first-p1.first))tb[pos].pop_back();
		else break;
	}
	tb[pos].push_back(x);
}
inline ll getval(pair<int,ll> x,int T)
{
	return x.second+1ll*A*T*T-2ll*A*T*x.first+B*T+C;
}
int main()
{
	scanf("%d%d%d%d%d",&n,&m,&A,&B,&C);
	B++;
	for(int i=1;i<=m;i++)
		scanf("%d%d%d%d",&s[i],&e[i],&p[i],&q[i]);
	for(int i=1;i<=m;i++)
	{
		R[p[i]].push_back(i);
	}
	tb[1].push_back(make_pair(0,0));
	for(int T=0;T<=1000;T++)
	{
		for(int j=0;j<R[T].size();j++)
		{
			int id=R[T][j];
			int st=s[id];
			while(!Q[st].empty()&&Q[st].top().first<=T)
			{
				insert(st,Q[st].top());
				Q[st].pop();
			}
			ll mnv;
			if(tb[st].size()==0)continue;
			int l=1,r=tb[st].size()-1,pos=0;
			mnv=getval(tb[st][0],T);
			while(l<=r)
			{
				int mid=(l+r)>>1;
				mnv=min(mnv,min(getval(tb[st][mid],T),getval(tb[st][mid-1],T)));
				if(getval(tb[st][mid],T)>getval(tb[st][mid-1],T))r=mid-1;
				else pos=mid,l=mid+1;
			}
			mnv=min(mnv,getval(tb[st][pos],T));
			Q[e[id]].push(make_pair(q[id],mnv+q[id]-p[id]));
		}
	}
	while(!Q[n].empty())
	{
		insert(n,Q[n].top());
		Q[n].pop();
	}
	ll ans=1e18;
	for(int i=0;i<tb[n].size();i++)ans=min(ans,tb[n][i].second-A*tb[n][i].first*tb[n][i].first+B*tb[n][i].first);
	printf("%lld\n",ans);
//	printf("%lld\n",tb[n][0].second-A*tb[n][0].first*tb[n][0].first+B*tb[n][0].first);
//	getchar();getchar();
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #1822.49 us5 MB + 428 KBAcceptedScore: 5

Testcase #2825.34 us5 MB + 428 KBAcceptedScore: 5

Testcase #3811.01 us5 MB + 424 KBAcceptedScore: 5

Testcase #4820.41 us5 MB + 424 KBAcceptedScore: 5

Testcase #51.353 ms5 MB + 524 KBAcceptedScore: 5

Testcase #61.63 ms5 MB + 560 KBAcceptedScore: 5

Testcase #71.488 ms5 MB + 548 KBAcceptedScore: 5

Testcase #81.639 ms5 MB + 568 KBAcceptedScore: 5

Testcase #91.62 ms5 MB + 552 KBAcceptedScore: 5

Testcase #101.287 ms5 MB + 516 KBAcceptedScore: 5

Testcase #111.335 ms5 MB + 528 KBAcceptedScore: 5

Testcase #121.387 ms5 MB + 540 KBAcceptedScore: 5

Testcase #131.362 ms5 MB + 532 KBAcceptedScore: 5

Testcase #141.425 ms5 MB + 544 KBAcceptedScore: 5

Testcase #1529.81 ms10 MB + 1016 KBAcceptedScore: 5

Testcase #1629.263 ms10 MB + 884 KBAcceptedScore: 5

Testcase #1727.556 ms10 MB + 304 KBAcceptedScore: 5

Testcase #1822.52 ms9 MB + 752 KBAcceptedScore: 5

Testcase #1936.074 ms11 MB + 864 KBAcceptedScore: 5

Testcase #2024.845 ms9 MB + 928 KBAcceptedScore: 5


Judge Duck Online | 评测鸭在线
Server Time: 2024-10-05 10:58:44 | Loaded in 2 ms | Server Status
个人娱乐项目,仅供学习交流使用