제출 #228834

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
228834		osaaateiasavtnl	Salesman (IOI09_salesman)	C++14	31 / 100	3098 ms	51324 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_pos(int i, int j) {
    return a[i].pos < a[j].pos;
}   
vector <int> who[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;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].day >> a[i].pos >> a[i].cost;
        who[a[i].day].app(i);
    }   

    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);
        int sz = who[d].size();

        for (int sl = 0; sl < sz; ++sl) {
            int i = who[d][sl];
            int cur = max(l.get(a[i].pos) - a[i].pos * D, r.get(N - a[i].pos) + a[i].pos * U);
            int prv = a[i].pos;
            for (int sr = sl; sr < sz; ++sr) {
                int i = who[d][sr];
                int x = a[i].pos;
                cur -= D * (x - prv);
                cur += a[i].cost;
                dp[x] = max(dp[x], cur);
                prv = x;
            }   
        }   
        for (int sr = 0; sr < sz; ++sr) {
            int i = who[d][sr];
            int cur = max(l.get(a[i].pos) - a[i].pos * D, r.get(N - a[i].pos) + a[i].pos * U);
            int prv = a[i].pos;
            for (int sl = sr; sl >= 0; --sl) {
                int i = who[d][sl];
                int x = a[i].pos;
                cur -= U * (prv - x);
                cur += a[i].cost;
                dp[x] = max(dp[x], cur);
                prv = x;                
            }   
        }   

        for (int i : who[d]) {
            int x = a[i].pos;

            //cout << i << " : " << dp[x] << endl;

            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: 31 / 100