oj.uz

Submission #44156

# Submission time Handle Problem Language Result Execution time Memory
44156 2018-03-30T08:54:17 Z faustaadp Fireworks (APIO16_fireworks) C++17
19 / 100
 102 ms 1632 KB 
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,m,i,ta,a[202020],has,d[330][330];
vector<ll> v[330],w[330];
ll depe(ll aa,ll bb)
{
	if(v[aa].size()==0)
		return bb;
	if(d[aa][bb]==-1)
	{
		d[aa][bb]=0;
		ll ii,jj;
		for(jj=0;jj<v[aa].size();jj++)	
		{
			ll hh=1e18;
			for(ii=0;ii<=bb;ii++)
				hh=min(hh,depe(v[aa][jj],ii)+abs(w[aa][jj]-(bb-ii)));	
			d[aa][bb]+=hh;
		}
	}
	return d[aa][bb];
}
ll hey(ll aa)
{
	ll ii,h=0;
	for(ii=2;ii<=n+m;ii++)
		h+=abs(a[ii]-aa);
	return h;
}
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(i=2;i<=n+m;i++)
	{
		cin>>ta>>a[i];
		v[ta].pb(i);
		w[ta].pb(a[i]);
	}
	has=1e18;
	if(n+m<=300)
	{
		memset(d,-1,sizeof(d));
		for(i=0;i<=300;i++)
			has=min(has,depe(1,i));
		//cout<<depe(4,3)<<"\n";
		//cout<<depe(1,14)<<"\n";
		cout<<has<<"\n";
	}
	else
	{
		ll L=0,R=1e18,C1,C2,CC1,CC2;
		while(L<=R)
		{
			C1=L+(R-L)/3;
			C2=R-(R-L)/3;
			CC1=hey(C1);
			CC2=hey(C2);
			if(CC1<CC2)
				R=C2-1;
			else
				L=C1+1;
			has=min(has,min(CC1,CC2));
		}
		cout<<has<<"\n";
	}
}

Compilation message

fireworks.cpp: In function 'long long int depe(long long int, long long int)':
fireworks.cpp:18:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(jj=0;jj<v[aa].size();jj++) 
            ~~^~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1384 KB Output is correct
2 Correct 13 ms 1444 KB Output is correct
3 Correct 18 ms 1444 KB Output is correct
4 Correct 29 ms 1444 KB Output is correct
5 Correct 37 ms 1452 KB Output is correct
6 Correct 39 ms 1452 KB Output is correct
7 Correct 45 ms 1452 KB Output is correct
8 Correct 54 ms 1452 KB Output is correct
9 Correct 58 ms 1460 KB Output is correct
10 Correct 61 ms 1460 KB Output is correct
11 Correct 67 ms 1460 KB Output is correct
12 Correct 75 ms 1468 KB Output is correct
13 Correct 78 ms 1492 KB Output is correct
14 Correct 91 ms 1620 KB Output is correct
15 Correct 102 ms 1620 KB Output is correct
16 Correct 85 ms 1620 KB Output is correct
17 Correct 87 ms 1632 KB Output is correct
18 Correct 86 ms 1632 KB Output is correct
19 Correct 87 ms 1632 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1272 KB Output isn't correct
2 Halted 0 ms 0 KB -