Submission #843364

#	Time	Username	Problem	Language	Result	Execution time	Memory
843364		asdfgrace	Salesman (IOI09_salesman)	C++17	Compilation error	0 ms	0 KiB

salesman

#include <bits/stdc++.h>
using namespace std;
 
/*
 * 2 st
 * first one assumes you are travelling from the left (downstream - i increases)
 * second one assumes you are travelling from the right (upstream - i decreases)
 */
 
 
#define DEBUG(x) //x
#define A(x) DEBUG(assert(x))
#define PRINT(x) DEBUG(cerr << x)
#define PV(x) DEBUG(cerr << #x << " = " << x << '\n')
#define PV2(x) DEBUG(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define PAR(x) DEBUG(PRINT(#x << " = { "); for (auto y : x) PRINT(y << ' '); PRINT("}\n");)
#define PAR2(x) DEBUG(PRINT(#x << " = { "); for (auto [y, z] : x) PRINT(y << ',' << z << "  "); PRINT("}\n");)
#define PAR2D(x) DEBUG(PRINT(#x << ":\n"); for (auto arr : x) {PAR(arr);} PRINT('\n'));
 
 
const int ninf = -2e9;
 
template <class T> struct SegTree {
  T comb(T a, T b) {
    return max(a, b);
  }
  const T init = ninf;
  vector<T> st;
  int n;
  
  SegTree(int len) {
    n = len;
    st = vector<T>(n * 2, init);
  }
  
  void upd(int k, T x) {
    k += n;
    st[k] = x;
    for (k /= 2; k >= 1; k /= 2) {
      st[k] = comb(st[2 * k], st[2 * k + 1]);
    }
  }
  
  T quer(int l, int r) {
    T res = init;
    l += n; r += n;
    for (; l <= r && l > 0 && r > 0 ; l >>= 1, r >>= 1) {
      if (l & 1) res = comb(res, st[l++]);
      if (!(r & 1)) res = comb(res, st[r--]);
    }
    return res;
  }
};
 
int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  const int N = 500100, T = 5010;
  int n, u, d, s;
  cin >> n >> u >> d >> s;
  if (n > 5000) {
    vector<array<int, 3>> a(n);
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < 3; ++j) {
        cin >> a[i][j];
      }
    }
    sort(a.begin(), a.end());
    SegTree<int> l(N), r(N);
    for (int i = 0; i < N; ++i) {
      l.upd(i, ninf + d * i);
      r.upd(i, ninf - u * i);
    }
    l.upd(s, d * s);
    r.upd(s, -u * s);
    for (int i = 0; i < n; ++i) {
      int best = l.st[a[i][1] + N] - d * a[i][1];
      int mxl = a[i][2] - d * a[i][1] + l.quer(0, a[i][1]);
      int mxr = a[i][2] + u * a[i][1] + r.quer(a[i][1], N - 1);
      best = max(best, max(mxl, mxr));
      l.upd(a[i][1], best + d * a[i][1]);
      r.upd(a[i][1], best - u * a[i][1]);
    }
    int ans = 0;
    for (int i = 0; i < N; ++i) {
      ans = max(ans, l.st[i + N] - d * i - (i < s ? d * (s - i) : u * (i - s)));
    }
    cout << ans << '\n';
  } else {
    vector<array<long long, 2>> at[T];
    for (int i = 0; i < n; ++i) {
      long long t, x, p;
      cin >> t >> x >> p;
      at[t].push_back({x, p});
    }
    vector<long long> l(T), r(T), sum(T), pmn(T), smx(T);
    vector<long long> cur(T, ninf), next(T, ninf);
    cur[s] = next[s] = 0;
    for (int t = 0; t < T; ++t) {
      if (!at[t].size()) continue;
      fill(l.begin(), l.end(), -d);
      fill(r.begin(), r.end(), -u);
      fill(sum.begin(), sum.end(), -d - u);
      for (auto [x, p] : at[t]) {
        l[x] += p;
        r[x] += p;
        sum[x] += p;
      }
      for (int i = 1; i < T; ++i) {
        l[i] += l[i - 1];
        r[i] += r[i - 1];
        sum[i] += sum[i - 1];
      }
      pmn[0] = sum[0];
      for (int i = 1; i < T; ++i) {
        pmn[i] = min(pmn[i - 1], sum[i]);
      }
      smx[T - 1] = sum[T - 1];
      for (int i = T - 2; i >= 0; --i) {
        smx[i] = max(smx[i + 1], sum[i]);
      }
      if (t == 2) {
        PAR(sum); PAR(pmn);
      }
      for (int i = 1; i < T; ++i) {
        if (cur[i] == ninf) continue;
        for (auto [x, p] : at[t]) {
          long long prof = 0;
          if (x > i) {
            prof = l[x] - l[i];
          } else {
            prof = r[i] - r[x];
          }
          PV(prof);
          prof += max(sum[min(i, x)] - pmn[min(i, x)], (x < i ? p : 0));
          PV(sum[min(i, x)]); PV(pmn[min(i, x)]);
          PV(prof);
          prof += smx[max(i, x)] - sum[max(i, x)];
          PV(x); PV(i); PV(prof); PV(cur[i]); PRINT('\n');
          next[x] = max(next[x], cur[i] + prof);
        }
      }
      cur = next;
    }
    long long ans = 0;
    for (int i = 0; i < T; ++i) {
      ans = max(ans, cur[i] - (i < s ? d * (s - i) : u * (i - s)));
    }
    cout << ans << '\n';
  }
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:134:35: error: no matching function for call to 'min(int&, std::tuple_element<0, std::array<long long int, 2> >::type&)'
  134 |           prof += max(sum[min(i, x)] - pmn[min(i, x)], (x < i ? p : 0));
      |                                   ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from salesman.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
salesman.cpp:134:35: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::tuple_element<0, std::array<long long int, 2> >::type' {aka 'long long int'})
  134 |           prof += max(sum[min(i, x)] - pmn[min(i, x)], (x < i ? p : 0));
      |                                   ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from salesman.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
salesman.cpp:134:35: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::tuple_element<0, std::array<long long int, 2> >::type' {aka 'long long int'})
  134 |           prof += max(sum[min(i, x)] - pmn[min(i, x)], (x < i ? p : 0));
      |                                   ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from salesman.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
salesman.cpp:134:35: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  134 |           prof += max(sum[min(i, x)] - pmn[min(i, x)], (x < i ? p : 0));
      |                                   ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from salesman.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
salesman.cpp:134:35: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  134 |           prof += max(sum[min(i, x)] - pmn[min(i, x)], (x < i ? p : 0));
      |                                   ^
salesman.cpp:134:52: error: no matching function for call to 'min(int&, std::tuple_element<0, std::array<long long int, 2> >::type&)'
  134 |           prof += max(sum[min(i, x)] - pmn[min(i, x)], (x < i ? p : 0));
      |                                                    ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from salesman.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
salesman.cpp:134:52: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::tuple_element<0, std::array<long long int, 2> >::type' {aka 'long long int'})
  134 |           prof += max(sum[min(i, x)] - pmn[min(i, x)], (x < i ? p : 0));
      |                                                    ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from salesman.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
salesman.cpp:134:52: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::tuple_element<0, std::array<long long int, 2> >::type' {aka 'long long int'})
  134 |           prof += max(sum[min(i, x)] - pmn[min(i, x)], (x < i ? p : 0));
      |                                                    ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from salesman.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
salesman.cpp:134:52: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  134 |           prof += max(sum[min(i, x)] - pmn[min(i, x)], (x < i ? p : 0));
      |                                                    ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from salesman.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
salesman.cpp:134:52: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  134 |           prof += max(sum[min(i, x)] - pmn[min(i, x)], (x < i ? p : 0));
      |                                                    ^
salesman.cpp:137:31: error: no matching function for call to 'max(int&, std::tuple_element<0, std::array<long long int, 2> >::type&)'
  137 |           prof += smx[max(i, x)] - sum[max(i, x)];
      |                               ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from salesman.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
salesman.cpp:137:31: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::tuple_element<0, std::array<long long int, 2> >::type' {aka 'long long int'})
  137 |           prof += smx[max(i, x)] - sum[max(i, x)];
      |                               ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from salesman.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
salesman.cpp:137:31: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::tuple_element<0, std::array<long long int, 2> >::type' {aka 'long long int'})
  137 |           prof += smx[max(i, x)] - sum[max(i, x)];
      |                               ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from salesman.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
salesman.cpp:137:31: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  137 |           prof += smx[max(i, x)] - sum[max(i, x)];
      |                               ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from salesman.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
salesman.cpp:137:31: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  137 |           prof += smx[max(i, x)] - sum[max(i, x)];
      |                               ^
salesman.cpp:137:48: error: no matching function for call to 'max(int&, std::tuple_element<0, std::array<long long int, 2> >::type&)'
  137 |           prof += smx[max(i, x)] - sum[max(i, x)];
      |                                                ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from salesman.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
salesman.cpp:137:48: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::tuple_element<0, std::array<long long int, 2> >::type' {aka 'long long int'})
  137 |           prof += smx[max(i, x)] - sum[max(i, x)];
      |                                                ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from salesman.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
salesman.cpp:137:48: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::tuple_element<0, std::array<long long int, 2> >::type' {aka 'long long int'})
  137 |           prof += smx[max(i, x)] - sum[max(i, x)];
      |                                                ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from salesman.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
salesman.cpp:137:48: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  137 |           prof += smx[max(i, x)] - sum[max(i, x)];
      |                                                ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from salesman.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
salesman.cpp:137:48: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  137 |           prof += smx[max(i, x)] - sum[max(i, x)];
      |                                                ^