oj.uz

Submission #241204

# Submission time Handle Problem Language Result Execution time Memory
241204 2020-06-23T10:04:49 Z osaaateiasavtnl Long Distance Coach (JOI17_coach) C++17
0 / 100
 5 ms 512 KB 
#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

const int INF = 3e18;

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];
    s.app(x);
    s.insert(s.begin(), 0);

    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) {
        //d + k * t <= x
        //k * t <= x - d

        if (x < d)
            return 0ll;

        int k = (x-d)/t;
        return k + 1;
    };  
    auto get = [&](int i, int j) {
        int di = a[i].f, dj = a[j%a.size()].f;
        for (int p = 0; p + 1 < s.size(); ++p) {
            if (getcnt(s[p+1], di) > getcnt(s[p+1], dj) || (getcnt(s[p+1], di) == getcnt(s[p+1], dj) && di > dj)) {
                return a[i].s + (getcnt(s[p+1], di)-1)*w;
            }
        }
        return INF;
    };
    auto save = [&](int i) {
        if (i == a.size())
            return 0ll;
        int cnt = x/t+(a[i].f<=x%t);
        return cnt * w;
    };

    vector <int> dp(a.size()+1, INF);
    dp[0] = (x/t+1)*w;
    for (int i = 0; i < a.size(); ++i) {
        int cur = 0;
        for (int j = i + 1; j <= a.size(); ++j) {
            if (j > i + 1) {
                cur += get(j - 1, i);
                cur = min(cur, INF);
            }   

            //cout << i << "->" << j << " : " << dp[i]+cur+save(j) << endl;

            dp[j] = min(dp[j], dp[i]+cur+save(j));
        }   
    }   

    #ifdef HOME
    cout << "water " << w << endl;        
    for (int i = 0; i <= a.size(); ++i) 
        cout << dp[i] << ' ';
    cout << endl;
    #endif

    cout << dp[a.size()] << endl;
}

Compilation message

coach.cpp: In lambda function:
coach.cpp:54:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int p = 0; p + 1 < s.size(); ++p) {
                         ~~~~~~^~~~~~~~~~
coach.cpp: In lambda function:
coach.cpp:62:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i == a.size())
             ~~^~~~~~~~~~~
coach.cpp: In function 'int main()':
coach.cpp:70:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a.size(); ++i) {
                     ~~^~~~~~~~~~
coach.cpp:72:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = i + 1; j <= a.size(); ++j) {
                             ~~^~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 304 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Incorrect 5 ms 512 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 304 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Incorrect 5 ms 512 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 304 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Incorrect 5 ms 512 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 304 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Incorrect 5 ms 512 KB Output isn't correct
8 Halted 0 ms 0 KB -