| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 921501 |
2024-02-04T03:22:00 Z |
gs25 |
Salesman (IOI09_salesman) |
C++17 |
|
3000 ms |
57580 KB |
#include <bits/stdc++.h>
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, n) for (int i = 1; i <= n; ++i)
#define ff first
#define ss second
using namespace std;
typedef long long ll;
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V> void __print(const pair<T, V> &x) {
cerr << '{';
__print(x.first);
cerr << ", ";
__print(x.second);
cerr << '}';
}
template <typename T> void __print(const T &x) {
int f = 0;
cerr << '{';
for (auto &i : x)
cerr << (f++ ? ", " : ""), __print(i);
cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V> void _print(T t, V... v) {
__print(t);
if (sizeof...(v))
cerr << ", ";
_print(v...);
}
#ifndef ONLINE_JUDGE
#define dbg(x...) \
cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \
_print(x); \
cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif
int N,U,S,D;
const int MAXN = 500010;
vector<pair<int,int>> fuck[MAXN];
struct segment_tree{
int n; vector<int> seg;
const int inf = 1e9;
segment_tree(int x){
n = x+1;
seg.resize(4*n+8,-inf);
}
void update(int node, int s, int e, int pos, int val){
if(pos<s||pos>e) return;
if(s==e){
seg[node] = val; return;
}
int m = s+e>>1;
update(2*node,s,m,pos,val);
update(2*node+1,m+1,e,pos,val);
seg[node] = max(seg[2*node],seg[2*node+1]);
return;
}
int query(int node, int s, int e, int l, int r){
if(r<s||l>e) return -inf;
if(l<=s&&e<=r) return seg[node];
int m = s+e>>1;
return max(query(2*node,s,m,l,r),query(2*node+1,m+1,e,l,r));
}
void update(int pos, int val){
return update(1,0,n,pos,val);
}
int query(int l, int r){
return query(1,0,n,l,r);
}
};
const int inf = 1e9;
int bada(int pos, int M, segment_tree& seg1, segment_tree& seg2){
int lmax = M - D*pos + seg1.query(0,pos);
int rmax = M + U*pos + seg2.query(pos,MAXN-1);
dbg(lmax,rmax);
int MM = max(lmax,rmax);
return MM;
}
int tmp1[MAXN],tmp2[MAXN];
void solve(){
cin >> N >> U >> D >> S;
rep(i,N){
int t,pos,M; cin >> t >> pos >> M;
fuck[t].pb({pos,M});
}
fuck[0].pb({S,0});
fuck[MAXN-1].pb({S,0});
segment_tree seg1(MAXN+10), seg2(MAXN+10);
//rep(i,N) sort(all(fuck[i]));
seg1.update(S,D*S);
seg2.update(S,-U*S);
for(int i=1; i<MAXN; i++){
if(fuck[i].size()==0) continue;
sort(all(fuck[i]));
auto& vec = fuck[i];
int t = vec.size();
for(int i=0;i<t;i++){
auto& [pos,M] = vec[i];
dbg(pos,M);
tmp1[i] = bada(pos,M,seg1,seg2);
tmp2[i] = tmp1[i];
}
for(int i=1; i<t; i++){
tmp1[i] = max(tmp1[i],vec[i].second + tmp1[i-1]-D*(vec[i].first - vec[i-1].first));
}
for(int i=t-2;i>=0;i--){
tmp2[i] = max(tmp2[i],vec[i].second + tmp2[i+1]-U*(vec[i+1].first-vec[i].first));
}
for(int i=0; i<t; i++){
auto& [pos,M] = vec[i];
tmp1[i] = max(tmp1[i],tmp2[i]);
seg1.update(pos,tmp1[i]+D*pos);
seg2.update(pos,tmp1[i]-U*pos);
}
}
cout << tmp1[0];
}
int32_t main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t=1; //cin >> t;
while(t--) solve();
}
Compilation message
salesman.cpp: In member function 'void segment_tree::update(int, int, int, int, int)':
salesman.cpp:73:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
73 | int m = s+e>>1;
| ~^~
salesman.cpp: In member function 'int segment_tree::query(int, int, int, int, int)':
salesman.cpp:83:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
83 | int m = s+e>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
31576 KB |
Output is correct |
| 2 |
Correct |
9 ms |
31628 KB |
Output is correct |
| 3 |
Correct |
23 ms |
31672 KB |
Output is correct |
| 4 |
Correct |
65 ms |
31828 KB |
Output is correct |
| 5 |
Correct |
159 ms |
32436 KB |
Output is correct |
| 6 |
Correct |
583 ms |
34132 KB |
Output is correct |
| 7 |
Correct |
1464 ms |
38456 KB |
Output is correct |
| 8 |
Correct |
2892 ms |
44300 KB |
Output is correct |
| 9 |
Execution timed out |
3049 ms |
46300 KB |
Time limit exceeded |
| 10 |
Execution timed out |
3039 ms |
51032 KB |
Time limit exceeded |
| 11 |
Execution timed out |
3061 ms |
50984 KB |
Time limit exceeded |
| 12 |
Execution timed out |
3029 ms |
54160 KB |
Time limit exceeded |
| 13 |
Execution timed out |
3096 ms |
54788 KB |
Time limit exceeded |
| 14 |
Execution timed out |
3026 ms |
57280 KB |
Time limit exceeded |
| 15 |
Execution timed out |
3103 ms |
57580 KB |
Time limit exceeded |
| 16 |
Execution timed out |
3081 ms |
57296 KB |
Time limit exceeded |
| 17 |
Correct |
10 ms |
31576 KB |
Output is correct |
| 18 |
Correct |
17 ms |
31576 KB |
Output is correct |
| 19 |
Correct |
36 ms |
31576 KB |
Output is correct |
| 20 |
Correct |
79 ms |
31784 KB |
Output is correct |
| 21 |
Correct |
83 ms |
32080 KB |
Output is correct |
| 22 |
Correct |
149 ms |
32116 KB |
Output is correct |
| 23 |
Correct |
149 ms |
32012 KB |
Output is correct |
| 24 |
Correct |
149 ms |
32108 KB |
Output is correct |
| 25 |
Correct |
2870 ms |
42700 KB |
Output is correct |
| 26 |
Execution timed out |
3066 ms |
43952 KB |
Time limit exceeded |
| 27 |
Execution timed out |
3031 ms |
44928 KB |
Time limit exceeded |
| 28 |
Execution timed out |
3038 ms |
45804 KB |
Time limit exceeded |
| 29 |
Execution timed out |
3053 ms |
46732 KB |
Time limit exceeded |
| 30 |
Execution timed out |
3048 ms |
47180 KB |
Time limit exceeded |
