Submission #133789

#TimeUsernameProblemLanguageResultExecution timeMemory
133789figter001Salesman (IOI09_salesman)C++17
0 / 100
4 ms504 KiB
#include <bits/stdc++.h>

using namespace std;

#define debug(x) '[' << #x << " is: " << x << "] "
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int nax = 5e5 + 100;

int d[nax],l[nax],m[nax];
int n,U,D,s,len;
ll up[4*nax],dn[4*nax];
ll dp[nax];

void build(int n,int s,int e){
	if(s == e){
		up[n] = dp[s] + s * U;
		dn[n] = dp[s] - s * D;
		return;
	}
	build(n*2,s,(s+e)/2);
	build(n*2+1,(s+e)/2+1,e);
	up[n] = max(up[n*2] , up[n*2+1]);
	dn[n] = max(dn[n*2] , dn[n*2+1]);
}

void update(int n,int s,int e,int at){
	if(s > at || e < at)return;
	if(s == e){
		up[n] = dp[s] - s * U;
		dn[n] = dp[s] + s * D;
		return;
	}
	update(n*2,s,(s+e)/2,at);
	update(n*2+1,(s+e)/2+1,e,at);
	up[n] = max(up[n*2] , up[n*2+1]);
	dn[n] = max(dn[n*2] , dn[n*2+1]);
}

ll get(int n,int s,int e,int l,int r,int t){
	if(s > r || e < l)return -1e18;
	if(s >= l && e <= r){
		if(t == 0)return up[n];
		else if(t == 1)return dn[n];
	}
	return max( get(n*2,s,(s+e)/2,l,r,t) , get(n*2+1,(s+e)/2+1,e,l,r,t) );
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.precision(10);
	cout << fixed;
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
	#endif
	cin>>n>>U>>D>>s;
	n+=2;
	d[0] = -1;l[0] = s;
	d[n-1] = nax + 1;l[n-1] = s;
	len = s;
	for(int i=1;i<n;i++){
		cin>>d[i]>>l[i]>>m[i];
		len = max(len,l[i]);
	}
	len++;
	vector<int> idx;
	for(int i=0;i<n;i++)idx.push_back(i);
	sort(idx.begin(),idx.end(), [&] (int a,int b) {
		return d[a] < d[b];
	});
	for(int i=1;i<=len;i++)dp[i] = -1e10;
	dp[s] = 0;
	build(1,1,len);
	int lst = -1;
	for(int j=0;j<idx.size();j++){
		int i = idx[j];
		if(j == idx.size() - 1 || d[idx[j]] != d[idx[j+1]]){
			ll cur = -1e18;
			if(i != 0){
				cur = max(cur, get(1,1,len,1,l[i],1) + m[i] - D*l[i]);
				cur = max(cur, get(1,1,len,l[i],len,0) + m[i] + U*l[i]);
			}
			dp[l[i]] = max(dp[l[i]],cur);
			update(1,1,len,l[i]);
		}else{
			vector<int> e;
			while(j < idx.size() - 1 && d[idx[j]] == d[idx[j+1]]){
				e.push_back(idx[j++]);
			}
			e.push_back(idx[j]);
			sort(e.begin(),e.end(), [&] (int a,int b) {
				return l[a] < l[b];
			});
			for(int x = 0;x<e.size();x++){
				ll sum = 0;
				int a = e[x];
				for(int y=x;y<e.size();y++){
					int b = e[y];
					sum += m[b];
					dp[l[a]] = max(dp[l[a]] , get(1,1,len,l[b],len,0) + sum + U*l[a]);
				}
			}
			for(int x = 0;x<e.size();x++){
				ll sum = 0;
				int a = e[x];
				for(int y=x;y>=0;y--){
					int b = e[y];
					sum += m[b];
					dp[l[a]] = max(dp[l[a]] , get(1,1,len,1,l[b],1) + sum - D*l[a]);
				}
			}
			for(int a : e){
				update(1,1,len,l[a]);
			}
		}
	}
	cout << dp[s] << endl;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:78:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<idx.size();j++){
              ~^~~~~~~~~~~
salesman.cpp:80:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(j == idx.size() - 1 || d[idx[j]] != d[idx[j+1]]){
      ~~^~~~~~~~~~~~~~~~~
salesman.cpp:90:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(j < idx.size() - 1 && d[idx[j]] == d[idx[j+1]]){
          ~~^~~~~~~~~~~~~~~~
salesman.cpp:97:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int x = 0;x<e.size();x++){
                  ~^~~~~~~~~
salesman.cpp:100:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int y=x;y<e.size();y++){
                 ~^~~~~~~~~
salesman.cpp:106:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int x = 0;x<e.size();x++){
                  ~^~~~~~~~~
salesman.cpp:77:6: warning: unused variable 'lst' [-Wunused-variable]
  int lst = -1;
      ^~~
salesman.cpp:57:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen("input.txt","r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...