Submission #1264055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264055		DeltaStruct	Salesman (IOI09_salesman)	C++20	60 / 100	576 ms	43476 KiB

salesman

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main(){
  int n,u,d,m,s(5e5+1); cin >> n >> u >> d >> m; --m;
  vector<vector<pair<int,int>>> A(s); for (int i(0),a,b,c;i < n;++i){
    cin >> a >> b >> c; A[a-1].emplace_back(b-1,c);
  }
  A.back().emplace_back(m,0);
  for (auto& B:A) sort(B.begin(),B.end());
  vector<int> up(2*s,-1e18),down(2*s,-1e18);
  for (int i(s+m);i;i>>=1) up[i] = -u*m,down[i] = -d*(n-m);
  auto f = [&](int i) -> int {
    int ret = -1e18;
    for (int l(s),r(s+i);l < r;l>>=1,r>>=1){
      if (l&1) ret = max(ret,down[l++]+d*(n-i));
      if (r&1) ret = max(ret,down[--r]+d*(n-i));
    }
    for (int l(s+i),r(s+s);l < r;l>>=1,r>>=1){
      if (l&1) ret = max(ret,up[l++]+u*i);
      if (r&1) ret = max(ret,up[--r]+u*i);
    }
    return ret;
  };
  for (auto& B:A){
    int q = B.size(); vector<int> C(q),D(q);
    for (int i(0);i < q;++i){
      C[i] = f(B[i].first)+B[i].second;
      if (i) C[i] = max(C[i],C[i-1]+B[i].second);
    }
    for (int i(q-1);i > -1;--i){
      D[i] = f(B[i].first)+B[i].second;
      if (i!=q-1) D[i] = max(D[i],D[i+1]+B[i].second);
    }
    for (int i(0);i < q;++i) for (int k(s+B[i].first);k;k>>=1){
      up[k] = max(up[k],max(C[i],D[i])-u*B[i].first);
      down[k] = max(down[k],max(C[i],D[i])-d*(n-B[i].first));
    }
  }
  cout << up[s+m]+u*m << endl;
}

• Subtask 1: 60 / 100