Submission #1283878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283878		rexdino	Salesman (IOI09_salesman)	C++20	19 / 100	3097 ms	19932 KiB

salesman

#include <bits/stdc++.h>
#define fi first
#define se second
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define REP(i,a,b) for(int i=(a); i>=(b); --i)
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(i) (1LL << (i))
#define sz(v) (int)(v).size()
#define ALL(v) (v).begin(),(v).end()
#define printArr(a, n) for (int i=1; i<=n; ++i) cout << a[i] << " "; el;
#define el cout << "\n"
#define int ll
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int N = 500001 + 5;
const int mod = 1e9 + 7;
const int base = 311;
const ll INF = 1e18;


/// REXDINO FROM LTV HSGS ///
int n, U, D, S;
ll dp[N];

struct Data{
    ll t, pos, val, id;
    bool operator < (const Data &other) const {
        if (t == other.t) return pos < other.pos;
        return t < other.t;
    }
} a[N];

ll cost(int x1, int x2){
    if (x1 <= x2) return (x2 - x1) * D;
    return (x1 - x2) * U;
}


void solve(){
    cin >> n >> U >> D >> S;
    FOR(i, 1, n) {
        cin >> a[i].t >> a[i].pos >> a[i].val;
        a[i].id = i;
    }

    sort(a + 1, a + n + 1);
    memset(dp, -0x3f, sizeof dp);

    ll ans = 0;
    dp[0] = 0;
    a[0].pos = S;
    a[n + 1].pos = S;
    FOR(i, 1, n + 1){
        FOR(j, 0, i - 1){
            dp[i] = max(dp[i], dp[j] - cost(a[j].pos, a[i].pos) + a[i].val);
        }
    }

    cout << dp[n + 1];
}

signed main(){
    #define NAME "main"
    if (fopen(NAME".inp", "r")){
        freopen(NAME".inp", "r", stdin);
        freopen(NAME".ans", "w", stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int t = 1;
//    cin >> t;
    while(t--) solve();

    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 19 / 100