oj.uz

Submission #282514

# Submission time Handle Problem Language Result Execution time Memory
282514 2020-08-24T13:43:28 Z Berted Long Distance Coach (JOI17_coach) C++14
0 / 100
 0 ms 384 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#define ll __int128
#define pii pair<ll, int>
#define fst first
#define snd second
using namespace std;

const ll INF = 1e36;

ll x, w, t, c[16], p[16], s[16], cur = 0;
int n, m;
bool delet[16];

ll res = 5 * INF;

void BF(int d)
{
	if (d <= n)
	{
		//cout << "Current Depth : " << d << "\n";
		vector<int> ud;
		vector<pii> lel; ll temp = 0;
		for (int i = 0; i <= m; i++)
		{
			if (!delet[i])
			{
				ll R = (s[d + 1] - p[i]) / t;
				ll L = (s[d] - p[i] + t - 1) / t;
				if (L <= R)
				{
					lel.push_back({t * R + p[i], i});
					delet[i] = 1; cur += c[i];
					temp += w * (R - L + 1);
					ud.push_back(i);
				}
			}
		}
		//cout << "Depth : " << d << ", Delete All : " << cur << "\n";
		BF(d + 1);
		for (auto &x : ud) {delet[x] = 0; cur -= c[x];}
		sort(lel.begin(), lel.end(), greater<pii>());
		cur += temp;
		for (int i = 0; i < lel.size(); i++)
		{
			//cout << "Depth : " << d << ", Delete " << i << " : " << cur << "\n";
			BF(d + 1);
			delet[lel[i].snd] = 1;
			cur -= w;
			cur += c[lel[i].snd];
		}
		for (auto &x : ud) {delet[x] = 0; cur += w; cur -= c[x];}
		cur -= temp;
	}
	else {res = min(res, cur);}
}

string tost(ll x)
{
	string res = "";
	while (x)
	{
		res = (char)(x % 10 + '0') + res;	
		x /= 10;
	}
	if (res.size() == 0) {return "0";}
	return res;
}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	long long a, b, cc;
	cin >> a >> n >> m >> b >> cc; x = a; w = b; t = cc;
	for (int i = 1; i <= n; i++) 
	{
		long long x; cin >> x; s[i] = x;
	}
	for (int i = 1; i <= m; i++) 
	{
		long long x, y; cin >> x >> y; 
		p[i] = x; c[i] = y;
	}
	s[0] = 0; s[n + 1] = x;
	sort(s, s + n + 2);
	p[0] = 0; c[0] = INF;
	BF(0);
	cout << tost(res) << "\n";
	return 0;
}

Compilation message

coach.cpp: In function 'void BF(int)':
coach.cpp:45:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<__int128, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for (int i = 0; i < lel.size(); i++)
      |                   ~~^~~~~~~~~~~~

Subtask #1
0 / 16.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 29.0

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