oj.uz

답안 #228837

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
228837 2020-05-02T18:52:01 Z osaaateiasavtnl Salesman (IOI09_salesman) C++14
100 / 100
 611 ms 43384 KB 
#include<bits/stdc++.h>
using namespace std; 
#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 = 2e9; 
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;
        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]) {
            fl[i] = fr[i] = 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 i : who[d]) {
            int x = a[i].pos;
            fl[i] = max(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] = max(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);
        }   
    }
    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
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 17920 KB Output is correct
2 Correct 19 ms 17920 KB Output is correct
3 Correct 16 ms 18048 KB Output is correct
4 Correct 17 ms 18176 KB Output is correct
5 Correct 19 ms 18176 KB Output is correct
6 Correct 39 ms 18944 KB Output is correct
7 Correct 70 ms 20472 KB Output is correct
8 Correct 138 ms 23036 KB Output is correct
9 Correct 186 ms 25592 KB Output is correct
10 Correct 311 ms 33272 KB Output is correct
11 Correct 387 ms 33288 KB Output is correct
12 Correct 483 ms 38468 KB Output is correct
13 Correct 491 ms 38456 KB Output is correct
14 Correct 604 ms 43384 KB Output is correct
15 Correct 559 ms 43384 KB Output is correct
16 Correct 611 ms 43384 KB Output is correct
17 Correct 16 ms 17920 KB Output is correct
18 Correct 16 ms 17920 KB Output is correct
19 Correct 16 ms 18048 KB Output is correct
20 Correct 17 ms 18048 KB Output is correct
21 Correct 17 ms 18048 KB Output is correct
22 Correct 20 ms 18048 KB Output is correct
23 Correct 24 ms 18048 KB Output is correct
24 Correct 19 ms 18176 KB Output is correct
25 Correct 94 ms 20472 KB Output is correct
26 Correct 176 ms 22904 KB Output is correct
27 Correct 304 ms 26608 KB Output is correct
28 Correct 302 ms 26996 KB Output is correct
29 Correct 456 ms 30272 KB Output is correct
30 Correct 454 ms 30320 KB Output is correct