oj.uz

Submission #74104

# Submission time Handle Problem Language Result Execution time Memory
74104 2018-08-30T05:45:09 Z funcsr Salesman (IOI09_salesman) C++17
100 / 100
 901 ms 37076 KB 
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1000141919
#define MOD 1000000007
#define MAX_N (1<<19)
struct SegTree {
  int seg[MAX_N*2-1];
  SegTree() {
    rep(i, MAX_N*2-1) seg[i] = -INF;
  }
  int query(int a, int b, int k=0, int l=0,int r=MAX_N){
    if (b <= l || r <=a)return -INF;
    if (a<=l&&r<=b) return seg[k];
    return max(query(a,b,k*2+1,l,(l+r)/2), query(a,b,k*2+2,(l+r)/2,r));
  }
  void update(int k, int v) {
    k += MAX_N-1;
    seg[k] = v;
    while (k > 0) {
      k=(k-1)/2;
      seg[k]=max(seg[k*2+1],seg[k*2+2]);
    }
  }
};
SegTree segL, segR;

int N, D, U, S;
vector<P> G[500000];
int tmp[500001];
int dpval(int x) { return segR.seg[MAX_N-1+x]-x*D; }
//int dpval(int x) { int v = segR.seg[MAX_N-1+x];if (v!=-INF)assert(v-x*D == segL.seg[MAX_N-1+x]+x*U); return v==-INF?-INF:(v-x*D); }

inline void update(int x, int v) {
  segR.update(x, v+x*D);
  segL.update(x, v-x*U);
}

inline void chmax(int x, int v) {
  if (dpval(x) >= v) return;
  update(x, v);
}
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N >> D >> U >> S, S--;
  rep(i, N) {
    int time, pos, val;
    cin >> time >> pos >> val;
    pos--, time--;
    G[time].pb(P(pos, val));
  }
  update(S, 0);

  rep(t, 500000) {
    if (G[t].empty()) continue;
    sort(all(G[t]));
    if (G[t].size() == 1) {
      for (P p : G[t]) {
        int x = p._1, val = p._2;
        int e = val+max(segR.query(0, x+1)-x*D, segL.query(x, MAX_N)+x*U);
        chmax(x, e);
      }
    }
    else {
      for (P p : G[t]) tmp[p._1] = dpval(p._1);
      for (P p : G[t]) {
        int x = p._1, val = p._2;
        int e = val+max(segR.query(0, x+1)-x*D, segL.query(x, MAX_N)+x*U);
        chmax(x, e);
      }
      // rollback
      int *tmp2 = segL.seg+MAX_N-1;
      for (P p : G[t]) {
        int nval = dpval(p._1);
        tmp2[p._1] = tmp[p._1];
        tmp[p._1] = nval;
        update(p._1, tmp2[p._1]);
      }

      reverse(all(G[t]));
      for (P p : G[t]) {
        int x = p._1, val = p._2;
        int e = val+max(segR.query(0, x+1)-x*D, segL.query(x, MAX_N)+x*U);
        chmax(x, e);
      }
      for (P p : G[t]) chmax(p._1, tmp[p._1]);
    }
  }
  int m = max(segR.query(0, S+1)-S*D, segL.query(S, MAX_N)+S*U);
  cout << m << "\n";
  return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 20344 KB Output is correct
2 Correct 21 ms 20348 KB Output is correct
3 Correct 25 ms 20408 KB Output is correct
4 Correct 22 ms 20408 KB Output is correct
5 Correct 26 ms 20724 KB Output is correct
6 Correct 54 ms 21604 KB Output is correct
7 Correct 104 ms 22564 KB Output is correct
8 Correct 185 ms 24072 KB Output is correct
9 Correct 268 ms 25908 KB Output is correct
10 Correct 455 ms 30620 KB Output is correct
11 Correct 538 ms 30708 KB Output is correct
12 Correct 675 ms 33652 KB Output is correct
13 Correct 697 ms 33652 KB Output is correct
14 Correct 901 ms 37036 KB Output is correct
15 Correct 824 ms 37076 KB Output is correct
16 Correct 733 ms 37076 KB Output is correct
17 Correct 18 ms 37076 KB Output is correct
18 Correct 19 ms 37076 KB Output is correct
19 Correct 20 ms 37076 KB Output is correct
20 Correct 22 ms 37076 KB Output is correct
21 Correct 22 ms 37076 KB Output is correct
22 Correct 25 ms 37076 KB Output is correct
23 Correct 26 ms 37076 KB Output is correct
24 Correct 25 ms 37076 KB Output is correct
25 Correct 173 ms 37076 KB Output is correct
26 Correct 344 ms 37076 KB Output is correct
27 Correct 516 ms 37076 KB Output is correct
28 Correct 652 ms 37076 KB Output is correct
29 Correct 810 ms 37076 KB Output is correct
30 Correct 874 ms 37076 KB Output is correct