Submission #228823

#	Time	Username	Problem	Language	Result	Execution time	Memory
228823		osaaateiasavtnl	Salesman (IOI09_salesman)	C++14	60 / 100	834 ms	52060 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;
}   

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);
    }   
    if (ms.size() < n) {
        exit(1);
    }   

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

    sort(a + 1, a + n + 1, comp);

    vector <int> c = {S};
    for (int i = 1; i <= n; ++i)
        c.app(a[i].pos);
    sort(all(c));
    c.resize(unique(all(c)) - c.begin());        

    l.init(); r.init();                                                        
    l.add(S, S * D);
    r.add(N - S, -S*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;
        /*
        for (int x : c) {
            if (dp[x] != -INF) {
                if (x < a[i].pos)
                    nn = max(nn, dp[x] - (a[i].pos - x) * D + a[i].cost);
                else
                    nn = max(nn, dp[x] - (x - 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;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:59:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (ms.size() < n) {
         ~~~~~~~~~~^~~

• Subtask 1: 60 / 100