제출 #241219

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
241219		osaaateiasavtnl	Long Distance Coach (JOI17_coach)	C++17	71 / 100	2086 ms	8224 KiB

coach

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    int x, n, m, w, t;
    cin >> x >> n >> m >> w >> t;
 
    //first - d, second - c
 
    vector <int> s(n);
    for (int i = 0; i < n; ++i) 
        cin >> s[i];
    sort(all(s));
    s.app(x);
 
    vector <ii> a(m);
    for (int i = 0; i < m; ++i) 
        cin >> a[i].f >> a[i].s;
 
    sort(all(a));
    reverse(all(a));
    a.insert(a.begin(), mp(0, 0));
 
    auto getcnt = [&](int x, int d) {
        if (x < d)
            return 0ll; 
        int k = (x-d)/t;
        return k + 1;
    };  
    auto get = [&](int i, int j, int p) {
        int di = a[i].f;
        int dj = a[j%a.size()].f;
        return a[j].s + (getcnt(s[p], dj)-1)*w;
    };
    auto save = [&](int i) {
        if (i == a.size())
            return 0ll;
        int cnt = x/t+(a[i].f<=(x%t));
        return cnt * w;
    }; 
    vector <int> last(s.size()), mem(a.size(), s.size());
    for (int i = 0; i < s.size(); ++i) {
        last[i] = 0;
        for (int j = 1; j < a.size(); ++j) {
            if (getcnt(s[i], a[j].f) > getcnt(s[i], a[last[i]].f) || (getcnt(s[i], a[j].f) == getcnt(s[i], a[last[i]].f) && a[j].f > a[last[i]].f)) {
                last[i] = j;
            }   
        }   
        mem[last[i]] = min(mem[last[i]], i);
    }
    vector <int> dp(a.size()+1, -1);
    dp[0] = (x/t+1)*w;
    for (int i = 0; i < a.size(); ++i) {
        int cur = 0;
        int lf = -1;
        for (int j = i + 1; j <= a.size(); ++j) {
            if (j > i + 1) {
                if (mem[j - 1] != s.size()) {
                    if (lf == -1)
                        lf = mem[j - 1];
                    else
                        lf = min(lf, mem[j - 1]);
                }   
                if (lf == -1)
                    break;
                else
                    cur += get(i, j - 1, lf);
            }   
            if (dp[j] == -1) {
                dp[j] = dp[i]+cur+save(j);
            }   
            else {
                dp[j] = min(dp[j], dp[i]+cur+save(j));
            }
        }   
    }   
    cout << (int)dp[a.size()] << endl;
}

컴파일 시 표준 에러 (stderr) 메시지

coach.cpp: In lambda function:
coach.cpp:46:13: warning: unused variable 'di' [-Wunused-variable]
         int di = a[i].f;
             ^~
coach.cpp: In lambda function:
coach.cpp:51:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i == a.size())
             ~~^~~~~~~~~~~
coach.cpp: In function 'int main()':
coach.cpp:57:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < s.size(); ++i) {
                     ~~^~~~~~~~~~
coach.cpp:59:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 1; j < a.size(); ++j) {
                         ~~^~~~~~~~~~
coach.cpp:68:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a.size(); ++i) {
                     ~~^~~~~~~~~~
coach.cpp:71:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = i + 1; j <= a.size(); ++j) {
                             ~~^~~~~~~~~~~
coach.cpp:73:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (mem[j - 1] != s.size()) {

• Subtask 1: 16 / 16
• Subtask 2: 30 / 30
• Subtask 3: 25 / 25
• Subtask 4: 0 / 29