Submission #300076

# Submission time Handle Problem Language Result Execution time Memory
300076 2020-09-16T13:01:32 Z tatyam Salesman (IOI09_salesman) C++17
Compilation error
0 ms 0 KB
#define int int64_t
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3fffffff;
using pii = pair<int, int>;
using tuplis = array<int, 3>;
template<class T, class U> bool chmax(T& a, const U& b){ if(a < b){ a = b; return 1; } return 0; }
#define rep(n) for(int i = 0; i < n; i++)
#define rrep(n) for(int i = n; --i; )
#define each(i, a) for(auto&& i : a)
#define all(a) begin(a), end(a)
 
 
int n, u, d, s;
struct T{
    map<int, int> up;
    map<int, int, greater<int>> down;
    T(int s){
        up[s] = 0;
        down[s] = 0;
        up[1000000] = -INF;
        down[0] = -INF;
    }
    int operator[](int at){
        int ans = -INF;
        pii a = *up.lower_bound(at);
        chmax(ans, a.second - (a.first - at) * u);
        a = *down.lower_bound(at);
        chmax(ans, a.second - (at - a.first) * d);
        return ans;
    }
    void insert(int at, int val){
        auto p = up.try_emplace(at, -INF).first;
        if(chmax(p->second, val)){
            while(p != up.begin()){
                auto q = prev(p);
                if(p->second - q->second >= (p->first - q->first) * u) up.erase(q);
                else break;
            }
        }
        p = down.try_emplace(at, -INF).first;
        if(chmax(p->second, val)){
            while(p != down.begin()){
                auto q = prev(p);
                if(p->second - q->second >= (q->first - p->first) * d) down.erase(q);
                else break;
            }
        }
    }
};
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n >> u >> d >> s;
    T q(s);
    vector<tuplis> a(n);
    each(i, a) each(j, i) cin >> j;
    map<int, vector<pii>> b;
    each(i, a) b[i[0]].emplace_back(i[1], i[2]);
    a.clear();
    a.shrink_to_fit();
    for(auto& [_, a] : b){
        int n = a.size();
        sort(all(a));
        vector<int> up(n), down;
        rep(n) up[i] = q[a[i].first];
        down = up;
        rep(n){
            down[i] += a[i].second;
            if(i + 1 < n) chmax(down[i + 1], down[i] - (a[i + 1].first - a[i].first) * d);
        }
        rrep(n){
            up[i] += a[i].second;
            if(i) chmax(up[i - 1], up[i] - (a[i].first - a[i - 1].first) * u);
        }
        rep(n) q.insert(a[i].first, max(up[i], down[i]));
    }
    cout << q[s] << endl;
}

Compilation message

In file included from /usr/include/c++/9/cassert:43,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from salesman.cpp:2:
/usr/include/x86_64-linux-gnu/c++/9/bits/c++config.h:254:26: error: expected initializer before 'size_t'
  254 |   typedef __SIZE_TYPE__  size_t;
      |                          ^~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/c++config.h:255:28: error: expected initializer before 'ptrdiff_t'
  255 |   typedef __PTRDIFF_TYPE__ ptrdiff_t;
      |                            ^~~~~~~~~
In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from salesman.cpp:2:
/usr/include/assert.h:70:20: error: expected ',' or '...' before '__line'
   70 |       unsigned int __line, const char *__function)
      |                    ^~~~~~
salesman.cpp:1:13: error: variable or field '__assert_perror_fail' declared void
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' was not declared in this scope
In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from salesman.cpp:2:
/usr/include/assert.h:74:49: error: expected primary-expression before 'const'
   74 | extern void __assert_perror_fail (int __errnum, const char *__file,
      |                                                 ^~~~~
/usr/include/assert.h:75:7: error: expected primary-expression before 'unsigned'
   75 |       unsigned int __line, const char *__function)
      |       ^~~~~~~~
/usr/include/assert.h:75:28: error: expected primary-expression before 'const'
   75 |       unsigned int __line, const char *__function)
      |                            ^~~~~
salesman.cpp:1:13: error: 'int64_t' has not been declared
    1 | #define int int64_t
      |             ^~~~~~~
In file included from /usr/include/ctype.h:26,
                 from /usr/include/c++/9/cctype:42,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:35,
                 from salesman.cpp:2:
/usr/include/x86_64-linux-gnu/bits/types.h:31:28: error: expected initializer before '__u_short'
   31 | typedef unsigned short int __u_short;
      |                            ^~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:32:22: error: expected initializer before '__u_int'
   32 | typedef unsigned int __u_int;
      |                      ^~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:33:27: error: expected initializer before '__u_long'
   33 | typedef unsigned long int __u_long;
      |                           ^~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:38:26: error: expected initializer before '__int16_t'
   38 | typedef signed short int __int16_t;
      |                          ^~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:39:28: error: expected initializer before '__uint16_t'
   39 | typedef unsigned short int __uint16_t;
      |                            ^~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:40:20: error: expected initializer before '__int32_t'
   40 | typedef signed int __int32_t;
      |                    ^~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:41:22: error: expected initializer before '__uint32_t'
   41 | typedef unsigned int __uint32_t;
      |                      ^~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:43:25: error: expected initializer before '__int64_t'
   43 | typedef signed long int __int64_t;
      |                         ^~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:44:27: error: expected initializer before '__uint64_t'
   44 | typedef unsigned long int __uint64_t;
      |                           ^~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:52:18: error: expected initializer before '__quad_t'
   52 | typedef long int __quad_t;
      |                  ^~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:53:27: error: expected initializer before '__u_quad_t'
   53 | typedef unsigned long int __u_quad_t;
      |                           ^~~~~~~~~~
In file included from /usr/include/ctype.h:26,
                 from /usr/include/c++/9/cctype:42,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:35,
                 from salesman.cpp:2:
/usr/include/x86_64-linux-gnu/bits/types.h:124:25: error: expected initializer before '__dev_t'
  124 | __STD_TYPE __DEV_T_TYPE __dev_t; /* Type of device numbers.  */
      |                         ^~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:125:25: error: expected initializer before '__uid_t'
  125 | __STD_TYPE __UID_T_TYPE __uid_t; /* Type of user identifications.  */
      |                         ^~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:126:25: error: expected initializer before '__gid_t'
  126 | __STD_TYPE __GID_T_TYPE __gid_t; /* Type of group identifications.  */
      |                         ^~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:127:25: error: expected initializer before '__ino_t'
  127 | __STD_TYPE __INO_T_TYPE __ino_t; /* Type of file serial numbers.  */
      |                         ^~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:128:27: error: expected initializer before '__ino64_t'
  128 | __STD_TYPE __INO64_T_TYPE __ino64_t; /* Type of file serial numbers (LFS).*/
      |                           ^~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:129:26: error: expected initializer before '__mode_t'
  129 | __STD_TYPE __MODE_T_TYPE __mode_t; /* Type of file attribute bitmasks.  */
      |                          ^~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:130:27: error: expected initializer before '__nlink_t'
  130 | __STD_TYPE __NLINK_T_TYPE __nlink_t; /* Type of file link counts.  */
      |                           ^~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:131:25: error: expected initializer before '__off_t'
  131 | __STD_TYPE __OFF_T_TYPE __off_t; /* Type of file sizes and offsets.  */
      |                         ^~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:132:27: error: expected initializer before '__off64_t'
  132 | __STD_TYPE __OFF64_T_TYPE __off64_t; /* Type of file sizes and offsets (LFS).  */
      |                           ^~~~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
In file included from /usr/include/ctype.h:26,
                 from /usr/include/c++/9/cctype:42,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:35,
                 from salesman.cpp:2:
/usr/include/x86_64-linux-gnu/bits/types.h:135:27: error: expected initializer before '__clock_t'
  135 | __STD_TYPE __CLOCK_T_TYPE __clock_t; /* Type of CPU usage counts.  */
      |                           ^~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:136:26: error: expected initializer before '__rlim_t'
  136 | __STD_TYPE __RLIM_T_TYPE __rlim_t; /* Type for resource measurement.  */
      |                          ^~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:137:28: error: expected initializer before '__rlim64_t'
  137 | __STD_TYPE __RLIM64_T_TYPE __rlim64_t; /* Type for resource measurement (LFS).  */
      |                            ^~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:138:24: error: expected initializer before '__id_t'
  138 | __STD_TYPE __ID_T_TYPE __id_t;  /* General type for IDs.  */
      |                        ^~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:139:26: error: expected initializer before '__time_t'
  139 | __STD_TYPE __TIME_T_TYPE __time_t; /* Seconds since the Epoch.  */
      |                          ^~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:140:30: error: expected initializer before '__useconds_t'
  140 | __STD_TYPE __USECONDS_T_TYPE __useconds_t; /* Count of microseconds.  */
      |                              ^~~~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:141:31: error: expected initializer before '__suseconds_t'
  141 | __STD_TYPE __SUSECONDS_T_TYPE __suseconds_t; /* Signed count of microseconds.  */
      |                               ^~~~~~~~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
In file included from /usr/include/ctype.h:26,
                 from /usr/include/c++/9/cctype:42,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:35,
                 from salesman.cpp:2:
/usr/include/x86_64-linux-gnu/bits/types.h:153:29: error: expected initializer before '__blksize_t'
  153 | __STD_TYPE __BLKSIZE_T_TYPE __blksize_t;
      |                             ^~~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:158:28: error: expected initializer before '__blkcnt_t'
  158 | __STD_TYPE __BLKCNT_T_TYPE __blkcnt_t;
      |                            ^~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:159:30: error: expected initializer before '__blkcnt64_t'
  159 | __STD_TYPE __BLKCNT64_T_TYPE __blkcnt64_t;
      |                              ^~~~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:162:30: error: expected initializer before '__fsblkcnt_t'
  162 | __STD_TYPE __FSBLKCNT_T_TYPE __fsblkcnt_t;
      |                              ^~~~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:163:32: error: expected initializer before '__fsblkcnt64_t'
  163 | __STD_TYPE __FSBLKCNT64_T_TYPE __fsblkcnt64_t;
      |                                ^~~~~~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:166:30: error: expected initializer before '__fsfilcnt_t'
  166 | __STD_TYPE __FSFILCNT_T_TYPE __fsfilcnt_t;
      |                              ^~~~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:167:32: error: expected initializer before '__fsfilcnt64_t'
  167 | __STD_TYPE __FSFILCNT64_T_TYPE __fsfilcnt64_t;
      |                                ^~~~~~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:170:28: error: expected initializer before '__fsword_t'
  170 | __STD_TYPE __FSWORD_T_TYPE __fsword_t;
      |                            ^~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:172:27: error: expected initializer before '__ssize_t'
  172 | __STD_TYPE __SSIZE_T_TYPE __ssize_t; /* Type of a byte count, or error.  */
      |                           ^~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:175:33: error: expected initializer before '__syscall_slong_t'
  175 | __STD_TYPE __SYSCALL_SLONG_TYPE __syscall_slong_t;
      |                                 ^~~~~~~~~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:177:33: error: expected initializer before '__syscall_ulong_t'
  177 | __STD_TYPE __SYSCALL_ULONG_TYPE __syscall_ulong_t;
      |                                 ^~~~~~~~~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:181:9: error: '__off64_t' does not name a type
  181 | typedef __off64_t __loff_t; /* Type of file sizes and offsets (LFS).  */
      |         ^~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:182:9: error: '__quad_t' does not name a type
  182 | typedef __quad_t *__qaddr_t;
      |         ^~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:186:25: error: expected initializer before '__intptr_t'
  186 | __STD_TYPE __SWORD_TYPE __intptr_t;
      |                         ^~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/types.h:189:23: error: expected initializer before '__socklen_t'
  189 | __STD_TYPE __U32_TYPE __socklen_t;
      |                       ^~~~~~~~~~~
In file included from /usr/include/endian.h:60,
                 from /usr/include/ctype.h:39,
                 from /usr/include/c++/9/cctype:42,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:35,
                 from salesman.cpp:2:
/usr/include/x86_64-linux-gnu/bits/byteswap.h:45:1: error: expected initializer before '__bswap_32'
   45 | __bswap_32 (unsigned int __bsx)
      | ^~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/byteswap.h:108:17: error: '__uint64_t' does not name a type; did you mean '__uint8_t'?
  108 | static __inline __uint64_t
      |                 ^~~~~~~~~~
      |                 __uint8_t
In file included from /usr/include/c++/9/cctype:42,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:35,
                 from salesman.cpp:2:
/usr/include/ctype.h:79:33: error: expected initializer before '*' token
   79 | extern const unsigned short int **__ctype_b_loc (void)
      |                                 ^
/usr/include/ctype.h:81:14: error: '__int32_t' does not name a type; did you mean '__int8_t'?
   81 | extern const __int32_t **__ctype_tolower_loc (void)
      |              ^~~~~~~~~
      |              __int8_t
/usr/include/ctype.h:83:14: error: '__int32_t' does not name a type; did you mean '__int8_t'?
   83 | extern const __int32_t **__ctype_toupper_loc (void)
      |              ^~~~~~~~~
      |              __int8_t
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: expected ';' at end of member declaration
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
salesman.cpp:1:13: error: 'int64_t' does not name a type
    1 | #define int int64_t
      |             ^~~~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:35,
                 from salesman.cpp:2:
/usr/include/c++/9/cctype:64:11: error: '::isalnum' has not been declared
   64 |   using ::isalnum;
      |           ^~~~~~~
/usr/include/c++/9/cctype:65:11: error: '::isalpha' has not been declared
   65 |   using ::isalpha;
      |           ^~~~~~~
/usr/include/c++/9/cctype:66:11: error: '::iscntrl' has not been declared
   66 |   using ::iscntrl;
      |           ^~~~~~~
/usr/include/c++/9/cctype:67:11: error: '::isdigit' has not been declared
   67 |   using ::isdigit;
      |           ^~~~~~~
/usr/include/c++/9/cctype:68:11: error: '::isgraph' has not been declared
   68 |   using ::isgraph;
      |           ^~~~~~~
/usr/include/c++/9/cctype:69:11: error: '::islower' has not been declared
   69 |   using ::islower;
      |           ^~~~~~~
/usr/include/c++/9/cctype:70:11: error: '::isprint' has not been de