Submission #884205

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
884205	2023-12-06T18:13:10 Z	DAleksa	Long Distance Coach (JOI17_coach)	C++17	Compilation error	0 ms	0 KB

coach

#include <bits/stdc++.h>

using namespace std;

#define int long long

struct Line {
    int a;
    int b;
    long long eval(int x) { return a * 1LL * x + b; }
};

const int N = 2e5 + 10;

long long X, T;
int n, m, W;
long long a[N];
long long b[N], B[N];
long long c[N], C[N];
int order[N];
long long pref[N];
__int128 dp[N];
long long ind[N];
long long cnt[N];
vector<Line> lines;
vector<long long> all;
map<long long, int> start_to_index;

long long get(int x) {
    long long ans = 1e18;
    for(Line l : lines) ans = min(ans, l.eval(x));
    return ans;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> X >> n >> m >> W >> T;
	for(int i = 1; i <= n; i++) cin >> a[i];
	sort(a + 1, a + n + 1);
	for(int i = 1; i <= m; i++) cin >> B[i] >> C[i];
	for(int i = 1; i <= m; i++) order[i] = i;
	sort(order + 1, order + m + 1, [&](int i, int j) {
		return B[i] < B[j];
	});
	for(int i = 1; i <= m; i++) {
		b[i] = B[order[i]];
		c[i] = C[order[i]];
		all.push_back(b[i]);
		start_to_index[b[i]] = i;
		pref[i] = pref[i - 1] + c[i];
		cnt[i] = X / T + (b[i] <= X % T);
		ind[i] = -1;
	}
	sort(all.begin(), all.end());
	n++;
	a[n] = X;
//	for(int i : all) cout << i << " ";
//	cout << "\n";
	for(int i = n; i >= 1; i--) {
		int temp = a[i] % T;
		int index = lower_bound(all.begin(), all.end(), temp) - all.begin();
		index--;
		if(index == -1) continue;
		ind[start_to_index[(a[i] - (temp - all[index])) % T]] = a[i] - (temp - all[index]);
	}
//	for(int i = 1; i <= m; i++) cout << ind[i] << " ";
//	cout << "\n";
//    for(int i = 1; i <= m; i++) cout << cnt[i] << " ";
//    cout << "\n";
	for(int i = 1; i <= m; i++) {
		dp[i] = dp[i - 1] + W * cnt[i];
		if(ind[i] != -1) dp[i] = min(dp[i], (__int128)get(W * (ind[i] / T)) + pref[i] + W * i * (ind[i] / T));
		lines.push_back({-i, dp[i] - pref[i]});
	}
//	for(int i = 1; i <= m; i++) cout << dp[i] << " ";
//	cout << "\n";
	cout << dp[m] + (__int128)(X / T + 1) * W;
	return 0;
}

Compilation message

coach.cpp: In function 'int main()':
coach.cpp:74:30: warning: narrowing conversion of '(dp[i] - ((__int128)pref[i]))' from '__int128' to 'long long int' [-Wnarrowing]
   74 |   lines.push_back({-i, dp[i] - pref[i]});
      |                        ~~~~~~^~~~~~~~~
coach.cpp:78:7: error: ambiguous overload for 'operator<<' (operand types are 'std::ostream' {aka 'std::basic_ostream<char>'} and '__int128')
   78 |  cout << dp[m] + (__int128)(X / T + 1) * W;
      |  ~~~~ ^~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      |  |             |
      |  |             __int128
      |  std::ostream {aka std::basic_ostream<char>}
In file included from /usr/include/c++/10/istream:39,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from coach.cpp:1:
/usr/include/c++/10/ostream:166:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  166 |       operator<<(long __n)
      |       ^~~~~~~~
/usr/include/c++/10/ostream:170:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  170 |       operator<<(unsigned long __n)
      |       ^~~~~~~~
/usr/include/c++/10/ostream:174:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(bool) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  174 |       operator<<(bool __n)
      |       ^~~~~~~~
In file included from /usr/include/c++/10/ostream:784,
                 from /usr/include/c++/10/istream:39,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from coach.cpp:1:
/usr/include/c++/10/bits/ostream.tcc:91:5: note: candidate: 'std::basic_ostream<_CharT, _Traits>& std::basic_ostream<_CharT, _Traits>::operator<<(short int) [with _CharT = char; _Traits = std::char_traits<char>]'
   91 |     basic_ostream<_CharT, _Traits>::
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/istream:39,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from coach.cpp:1:
/usr/include/c++/10/ostream:181:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(short unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  181 |       operator<<(unsigned short __n)
      |       ^~~~~~~~
In file included from /usr/include/c++/10/ostream:784,
                 from /usr/include/c++/10/istream:39,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from coach.cpp:1:
/usr/include/c++/10/bits/ostream.tcc:105:5: note: candidate: 'std::basic_ostream<_CharT, _Traits>& std::basic_ostream<_CharT, _Traits>::operator<<(int) [with _CharT = char; _Traits = std::char_traits<char>]'
  105 |     basic_ostream<_CharT, _Traits>::
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/istream:39,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from coach.cpp:1:
/usr/include/c++/10/ostream:192:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  192 |       operator<<(unsigned int __n)
      |       ^~~~~~~~
/usr/include/c++/10/ostream:201:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long long int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  201 |       operator<<(long long __n)
      |       ^~~~~~~~
/usr/include/c++/10/ostream:205:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long long unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  205 |       operator<<(unsigned long long __n)
      |       ^~~~~~~~
/usr/include/c++/10/ostream:220:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(double) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  220 |       operator<<(double __f)
      |       ^~~~~~~~
/usr/include/c++/10/ostream:224:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(float) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  224 |       operator<<(float __f)
      |       ^~~~~~~~
/usr/include/c++/10/ostream:232:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long double) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  232 |       operator<<(long double __f)
      |       ^~~~~~~~
/usr/include/c++/10/ostream:511:5: note: candidate: 'std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, char) [with _CharT = char; _Traits = std::char_traits<char>]'
  511 |     operator<<(basic_ostream<_CharT, _Traits>& __out, char __c)
      |     ^~~~~~~~
/usr/include/c++/10/ostream:517:5: note: candidate: 'std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, char) [with _Traits = std::char_traits<char>]'
  517 |     operator<<(basic_ostream<char, _Traits>& __out, char __c)
      |     ^~~~~~~~
/usr/include/c++/10/ostream:523:5: note: candidate: 'std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, signed char) [with _Traits = std::char_traits<char>]'
  523 |     operator<<(basic_ostream<char, _Traits>& __out, signed char __c)
      |     ^~~~~~~~
/usr/include/c++/10/ostream:528:5: note: candidate: 'std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, unsigned char) [with _Traits = std::char_traits<char>]'
  528 |     operator<<(basic_ostream<char, _Traits>& __out, unsigned char __c)
      |     ^~~~~~~~