Submission #1137512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137512		Rufat	Salesman (IOI09_salesman)	C++20	5 / 100	3097 ms	45224 KiB

salesman

//Author RufatM
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<double> vd;
typedef vector<vector<double>> vvd;
typedef vector<ld> vld;
typedef vector<vector<ld>> vvld;
typedef vector<ull> vull;
typedef vector<vector<ull>> vvull;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef vector<pii> vpii;
typedef vector<vector<pii>> vvp;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define eb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ff first
#define ss second
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define pow(x, y) static_cast<int>(pow(x, y))
#define sz(x) (int)(x).sz()
#pragma GCC optimize("Ofast","unroll-loops","fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt")
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> s;
template<typename T> inline T sqr(T x) {return x*x;}
template<typename T> inline T modinv(T a, T mod){return 0;} 
template<class T> bool isPrime(T n){if(n<=1)return false;if(n<=3)return true;if(n%2==0||n%3==0)return false;for(T i=5;i*i<=n;i+=6)if(n%i==0||n%(i+2)==0)return false;return true;}
const int MOD = 1e9+7;
const int INF = 1e9 + 7;
const long long LINF = 1e18 + 7;
const int MAXN = 100;
struct Fair {
    int day, location;
    int profit;
};
ll u, d, s;
ll best = 0;
vector<Fair> fair;
ll cost(int l1, int l2) {
    if (l2 > l1) {
        return (l2 - l1) * d;
    } 
    else{
        return (l1 - l2) * u;
    }
}
void backtrack(int idx, int last, ll curr) {
    best = max(best, curr - cost(last, s));
    for (int next = idx + 1; next < fair.size(); next++) {
        if (fair[next].day >= fair[idx].day) {
            ll costt = cost(last, fair[next].location);
            backtrack(next, fair[next].location, curr - costt + fair[next].profit);
        }
    }
}
signed main() {
    fastio;
    int t = 1;
    // cin >> t;
    while (t--) {
        int n;
        cin >> n >> u >> d >> s;
        fair.resize(n);
        for (int i = 0; i < n; i++) {
            cin >> fair[i].day >> fair[i].location >> fair[i].profit;
        }
        sort(all(fair), [](const Fair& a, const Fair& b) {
            return a.day < b.day;
        });
        best = 0;
        for (int i = 0; i < n; i++) {
            ll costt = cost(s, fair[i].location);
            backtrack(i, fair[i].location, fair[i].profit - costt);
        }
        cout << best << endl;
    }
    return 0;
}

• Subtask 1: 5 / 100