oj.uz

답안 #831040

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
831040 2023-08-19T15:37:23 Z lalala56 Salesman (IOI09_salesman) C++17
100 / 100
 413 ms 51180 KB 
#include<bits/stdc++.h>
using namespace std;
#define PROB "Salesman"
#define ll long long
#define ull unsigned long long
#define FOR(i,a,b) for(int i=a;i<=b;(i)++)
#define FOD(i,a,b) for(int i=a;i>=b;(i)--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp make_pair
#define SZ(x) int(x.size())
#define bit(p,i) ((p>>i)&1)

template <class T>
inline bool minimize(T &x, const T &y){ if (x > y){x = y; return 1;} return 0; }

template <class T>
inline bool maximize(T &x, const T &y){ if (x < y){x = y; return 1;} return 0; }
const int N=6e5+9;
const ll inf=1e16;
int n;
ll U,D,S;
vector<int>a[N];
pll p[N];
ll f[2][N],dp[N];
void upd(int id,ll x,int ty){
    for(int i=id;i<N;i+=i&(-i))maximize(f[ty][i],x);
}
ll findd(int id,int ty){
    ll res=-inf;
    for(int i=id;i>0;i-=i&(-i))maximize(res,f[ty][i]);
    return res;
}
bool ss(int a,int b){
    return p[a].fi<p[b].fi;
}
void giai(){
    
    cin>>n>>U>>D>>S;
    FOR(i,1,N-1)f[0][i]=f[1][i]=-inf;
    upd(S,S*D,0);
    upd(N-S,-S*U,1);
    FOR(i,1,n){
        ll t,l,m;cin>>t>>l>>m;
        a[t].push_back(i);
        p[i]={l,m};
    }
    
    FOR(i,1,N-1){
        sort(a[i].begin(),a[i].end(),ss);
        vector<ll>tmp1(SZ(a[i])),tmp2(SZ(a[i]));
        //int cnt=0;
        FOR(j,0,SZ(a[i])-1){
            
            int v=a[i][j];
            //cout<<p[v].fi<<" ";
           //++cnt;
            ll l=findd(p[v].fi-1,0);
            ll r=findd(N-p[v].fi-1,1);
            dp[v]=max(l-p[v].fi*D,r+p[v].fi*U)+p[v].se;
            //cout<<i<<" "<<v<<" "<<l<<" "<<r<<" "<<dp[v]<<" "<<dp[v]+p[v].fi*D<<" "<<dp[v]-p[v].fi*U<<'\n';
            
        }
        //if(!a[i].empty())cout<<'\n';
        FOR(j,0,SZ(a[i])-1){
            int v=a[i][j];
            if(j==0)tmp1[j]=dp[v];
            else tmp1[j]=max(dp[v],tmp1[j-1]+p[v].se-(p[v].fi-p[a[i][j-1]].fi)*D);
            
        }
        FOD(j,SZ(a[i])-1,0){
            int v=a[i][j];
            if(j==SZ(a[i])-1)tmp2[j]=dp[v];
            else tmp2[j]=max(dp[v],tmp2[j+1]+p[v].se-(p[a[i][j+1]].fi-p[v].fi)*U);
            
        }
        FOR(j,0,SZ(a[i])-1){
            //cout<<dp[a[i][j]]<<" "<<tmp1[j]<<" "<<tmp2[j]<<'\n';
            maximize(dp[a[i][j]],max(tmp1[j],tmp2[j]));
        }
        //if(!a[i].empty())cout<<'\n';

        //if(cnt>1)cout<<i<<" "<<cnt<<'\n';

        for(int v:a[i]){
            upd(p[v].fi,dp[v]+p[v].fi*D,0);
            upd(N-p[v].fi,dp[v]-p[v].fi*U,1);
        }
        //cout<<'\n';
    }
    ll res=0;
    FOR(i,1,n){
        //cout<<dp[i]<<'\n';
        if(S>p[i].fi)maximize(res,dp[i]-(S-p[i].fi)*D);
        else maximize(res,dp[i]-(p[i].fi-S)*U);
    }
    cout<<res;

}
int main(){
    if(fopen(PROB".inp","r")){
        freopen(PROB".inp","r",stdin);
        freopen(PROB".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    giai();
    


}

Compilation message

salesman.cpp: In function 'int main()':
salesman.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         freopen(PROB".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen(PROB".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 13 ms 23924 KB Output is correct
5 Correct 14 ms 24084 KB Output is correct
6 Correct 24 ms 24892 KB Output is correct
7 Correct 44 ms 26548 KB Output is correct
8 Correct 77 ms 29272 KB Output is correct
9 Correct 119 ms 32128 KB Output is correct
10 Correct 215 ms 40244 KB Output is correct
11 Correct 234 ms 40140 KB Output is correct
12 Correct 312 ms 45676 KB Output is correct
13 Correct 314 ms 45712 KB Output is correct
14 Correct 400 ms 51132 KB Output is correct
15 Correct 379 ms 51148 KB Output is correct
16 Correct 413 ms 51180 KB Output is correct
17 Correct 12 ms 23764 KB Output is correct
18 Correct 13 ms 23768 KB Output is correct
19 Correct 13 ms 23776 KB Output is correct
20 Correct 14 ms 23824 KB Output is correct
21 Correct 13 ms 23892 KB Output is correct
22 Correct 14 ms 24008 KB Output is correct
23 Correct 14 ms 23892 KB Output is correct
24 Correct 14 ms 24016 KB Output is correct
25 Correct 58 ms 26760 KB Output is correct
26 Correct 90 ms 30096 KB Output is correct
27 Correct 158 ms 35108 KB Output is correct
28 Correct 168 ms 34824 KB Output is correct
29 Correct 230 ms 38124 KB Output is correct
30 Correct 229 ms 39724 KB Output is correct