oj.uz

답안 #1007547

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1007547 2024-06-25T07:16:41 Z huutuan Salesman (IOI09_salesman) C++14
80 / 100
 379 ms 65536 KB 
#include <bits/stdc++.h>

using namespace std;

const int N=5e5+10;
const int inf=2e9;

struct SegmentTree{
   int n;
   vector<int> t;
   void init(int _n){
      n=_n;
      t.assign(4*n+1, -inf);
   }
   void update(int k, int l, int r, int pos, int val){
      if (l==r){
         t[k]=val;
         return;
      }
      int mid=(l+r)>>1;
      if (pos<=mid) update(k<<1, l, mid, pos, val);
      else update(k<<1|1, mid+1, r, pos, val);
      t[k]=max(t[k<<1], t[k<<1|1]);
   }
   int get(int k, int l, int r, int L, int R){
      if (r<L || R<l) return -inf;
      if (L<=l && r<=R) return t[k];
      int mid=(l+r)>>1;
      return max(get(k<<1, l, mid, L, R), get(k<<1|1, mid+1, r, L, R));
   }
} st1, st2;

int n, s, f[N], f1[N], f2[N], val[N], tt[N];
int u, d;
set<int> st;
vector<int> v[N];

void calc(int t){
   vector<int> &vv=v[t];
   sort(vv.begin(), vv.end());
   for (auto &i:vv){
      f1[i]=f2[i]=max(st1.get(1, 1, st1.n, 1, i)-d*i, st2.get(1, 1, st2.n, i, st2.n)+u*i);
   }
   f2[vv[0]]+=val[vv[0]];
   f1[vv.back()]+=val[vv.back()];
   for (int i=1; i<(int)vv.size(); ++i) f2[vv[i]]=max(f2[vv[i]], f2[vv[i-1]]-d*(vv[i]-vv[i-1]))+val[vv[i]];
   for (int i=(int)vv.size()-2; i>=0; --i) f1[vv[i]]=max(f1[vv[i]], f1[vv[i+1]]-u*(vv[i+1]-vv[i]))+val[vv[i]];
   for (int i:vv){
      f[i]=max(f1[i], f2[i]);
      st1.update(1, 1, st1.n, i, f[i]+d*i);
      st2.update(1, 1, st2.n, i, f[i]-u*i);
   }
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> u >> d >> s;
   for (int i=1; i<=n; ++i){
      int t, l, m; cin >> t >> l >> m;
      v[t].push_back(l);
      tt[l]=t;
      val[l]=m;
      st.insert(t);
   }
   st1.init(N); st2.init(N);
   st.insert(0);
   for (int i=0; i<N; ++i) f[i]=-inf;
   f[s]=0;
   st1.update(1, 1, st1.n, s, f[s]+d*s);
   st2.update(1, 1, st2.n, s, f[s]-u*s);
   v[0].push_back(s);
   v[500001].push_back(s);
   st.insert(500001);
   for (auto it=next(st.begin()); it!=st.end(); ++it){
      calc(*it);
   }
   cout << f[s] << '\n';
   return 0;
}

Subtask #1
80.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 37468 KB Output is correct
2 Correct 7 ms 37468 KB Output is correct
3 Correct 7 ms 37468 KB Output is correct
4 Correct 9 ms 37688 KB Output is correct
5 Correct 10 ms 37980 KB Output is correct
6 Correct 25 ms 39004 KB Output is correct
7 Correct 64 ms 41556 KB Output is correct
8 Correct 133 ms 45392 KB Output is correct
9 Correct 168 ms 49212 KB Output is correct
10 Correct 341 ms 61008 KB Output is correct
11 Correct 379 ms 60948 KB Output is correct
12 Runtime error 256 ms 65536 KB Execution killed with signal 9
13 Runtime error 231 ms 65536 KB Execution killed with signal 9
14 Runtime error 318 ms 65536 KB Execution killed with signal 9
15 Runtime error 336 ms 65536 KB Execution killed with signal 9
16 Runtime error 302 ms 65536 KB Execution killed with signal 9
17 Correct 6 ms 37464 KB Output is correct
18 Correct 7 ms 37468 KB Output is correct
19 Correct 7 ms 37468 KB Output is correct
20 Correct 8 ms 37484 KB Output is correct
21 Correct 9 ms 37468 KB Output is correct
22 Correct 9 ms 37724 KB Output is correct
23 Correct 9 ms 37468 KB Output is correct
24 Correct 10 ms 37724 KB Output is correct
25 Correct 63 ms 38120 KB Output is correct
26 Correct 113 ms 38736 KB Output is correct
27 Correct 199 ms 39400 KB Output is correct
28 Correct 245 ms 40804 KB Output is correct
29 Correct 273 ms 40276 KB Output is correct
30 Correct 283 ms 40140 KB Output is correct