Submission #74095

#	Time	Username	Problem	Language	Result	Execution time	Memory
74095		funcsr	Salesman (IOI09_salesman)	C++17	62 / 100	848 ms	36332 KiB

salesman

#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; }

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]) swap(tmp[p._1], tmp2[p._1]), 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: 62 / 100