| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 300076 | tatyam | Salesman (IOI09_salesman) | C++17 | Compilation error | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
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