Submission #228829

#	Time	Username	Problem	Language	Result	Execution time	Memory
228829		osaaateiasavtnl	Salesman (IOI09_salesman)	C++14	40 / 100	718 ms	65540 KiB

salesman

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC

const int N = 5e5 + 7;
const int INF = 1e18;

struct Fen {
int f[N];
void init() {
    for (int i = 0; i < N; ++i)
        f[i] = -INF;
}   
void add(int i, int x) {
    for (; i < N; i |= i + 1)
        f[i] = max(f[i], x);
}   
int get(int i) {
    int ans = -INF;
    for (; i >= 0; i &= i + 1, --i)
        ans = max(ans, f[i]);
    return ans;
}   
} l, r; // l - relax from l, r - relax from r 

int n, U, D, S;
struct Fair {
    int day, pos, cost;
} a[N];  
int dp[N];

bool comp(Fair a, Fair b) {
    return a.day < b.day;
}   
bool comp_pos(int i, int j) {
    return a[i].pos < a[j].pos;
}   

vector <int> who[N];
int fl[N], fr[N];

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

    cin >> n >> U >> D >> S;
    set <int> ms;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].day >> a[i].pos >> a[i].cost;
        ms.insert(a[i].day);
        who[a[i].day].app(i);
    }   

    for (int i = 0; i < N; ++i)
        dp[i] = -INF;
    dp[S] = 0;

    l.init(); r.init();                                                        
    l.add(S, S * D);
    r.add(N - S, -S*U);
    for (int d = 1; d < N; ++d) {
        sort(all(who[d]), comp_pos);
        for (int i : who[d]) {
            int x = a[i].pos;
            fl[i] = l.get(a[i].pos) - a[i].pos * D + a[i].cost;
            l.add(a[i].pos, fl[i] + x * D);
        }
        reverse(all(who[d]));
        for (int i : who[d]) {
            int x = a[i].pos;
            fr[i] = r.get(N - a[i].pos) + a[i].pos * U + a[i].cost;
            r.add(N - x, fr[i] - x * U);
        }   
        for (int i : who[d]) {
            int x = a[i].pos;
            dp[x] = max(dp[x], fl[i]);
            dp[x] = max(dp[x], fr[i]);
            l.add(x, dp[x] + x * D);
            r.add(N - x, dp[x] - x * U);
        }   
    }

    /*
    for (int i = 1; i <= n; ++i) {
        int x = a[i].pos;
        int nn = max(l.get(a[i].pos) - a[i].pos * D, r.get(N - a[i].pos) + a[i].pos * U) + a[i].cost;
        dp[x] = max(dp[x], nn);
        l.add(x, dp[x] + x * D);
        r.add(N - x, dp[x] - x * U);
    }
    */  

    int ans = 0;
    for (int i = 0; i <= S; ++i)
        ans = max(ans, dp[i] - D * (S - i));
    for (int i = S; i < N; ++i)
        ans = max(ans, dp[i] - U * (i - S));
    cout << ans << endl;
}

• Subtask 1: 40 / 100