Submission #235476

#	Time	Username	Problem	Language	Result	Execution time	Memory
235476		miello	Salesman (IOI09_salesman)	C++14	19 / 100	3097 ms	17228 KiB

salesman

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

const int MXN = 5e5 + 5;
const int INF = 1e9 + 7;

vector<iii> fair;

int dp[MXN], n, u, d, s;

int dist(int start, int stop) {
    int now, fi, sc;
    if(start == -1) {
        fi = s, sc = fair[stop].second.first;
    } else if(stop == -1) {
        fi = fair[start].second.first, sc = s;
    } else {
        fi = fair[start].second.first, sc = fair[stop].second.first;
    }
    if(fi < sc) {
        now = u * (sc - fi);
    } else {
        now = d * (fi - sc);
    }
    return now;
}

int main() {
    scanf("%d %d %d %d", &n, &u, &d, &s);
    for(int i = 0; i < n; i++) {
        int t, l, m;
        scanf("%d %d %d", &t, &l, &m);
        fair.emplace_back(t, ii(l, m));
    }
    if(u <= d) {
        sort(fair.begin(), fair.end(), [](iii a, iii b) {
            return a.first < b.first || (a.first == b.first && a.second.first > b.second.first);
        });
    } else {
        sort(fair.begin(), fair.end(), [](iii a, iii b) {
            return a.first < b.first || (a.first == b.first && a.second.first < b.second.first);
        });
    }
    fill(dp + 1, dp + MXN, -INF);
    for(int i = 1, stop = 0; i <= n; i++, stop++) {
        int mx = -INF;
        for(int j = 0, start = -1; j < i; j++, start++) {
            mx = max(mx, dp[j] - dist(start, stop));
        }
        dp[i] = mx + fair[stop].second.second;
    }
    int p = 0;
    for(int i = 1; i <= n; i++) {
        p = max(p, dp[i] - dist(i - 1, -1));
    }
    printf("%d", p);
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d", &n, &u, &d, &s);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &t, &l, &m);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 19 / 100