oj.uz

Submission #233145

# Submission time Handle Problem Language Result Execution time Memory
233145 2020-05-19T14:32:55 Z nicolaalexandra Semiexpress (JOI17_semiexpress) C++14
100 / 100
 13 ms 512 KB 
#include <bits/stdc++.h>
#define DIM 2010
using namespace std;
long long v[DIM],w[DIM];
long long n,m,k,a,b,c,t,i;

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m>>k>>a>>b>>c>>t;
    for (i=1;i<=m;i++)
        cin>>v[i];

    k -= m;

    /// mai intai vad cat ma pot extinde din statia i mergand doar cu tren normal
    for (i=1;i<=m;i++){
        long long timp = b * (v[i] - 1);
        /// timp + a * cnt <= t
        if (timp > t) /// inseamna ca nici macar aici nu pot ajunge
            w[i] = -1;
        else {
            if (i != m)
                w[i] = min ((t - timp) / a, v[i+1] - v[i] - 1);
        }
    }

    for (;k--;){
        /// adaug un tren long longre doua statii, iau varianta care imi aduce cele mai multe statii
        long long maxi = 0; int poz = 0;
        for (i=1;i<m;i++){
            if (w[i] == -1 || v[i+1] - v[i] - 1 == w[i])
                continue;

            /// v[i] + w[i] + 1 -> aici pun statie pt semiexpress

            long long timp = b * (v[i] - 1) + c * (w[i] + 1);
            if (timp > t) /// degeaba pun
                continue;

            /// timp + a * cnt <= t
            long long cnt = min ((t - timp) / a + 1, v[i+1] - (v[i] + w[i]) - 1);

            if (cnt > maxi)
                maxi = cnt, poz = i;
        }

        w[poz] += maxi;

    }

    long long sol = 0;
    for (i=1;i<=m;i++)
        sol += w[i] + 1;

    cout<<sol - 1;



    return 0;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 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 Correct 4 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 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 Correct 4 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 256 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 6 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 256 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 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 Correct 4 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 256 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 6 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 256 KB Output is correct
19 Correct 6 ms 384 KB Output is correct
20 Correct 7 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 6 ms 384 KB Output is correct
23 Correct 13 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 6 ms 384 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 6 ms 384 KB Output is correct
29 Correct 7 ms 288 KB Output is correct
30 Correct 6 ms 384 KB Output is correct