oj.uz

Submission #46642

# Submission time Handle Problem Language Result Execution time Memory
46642 2018-04-22T13:12:35 Z kuzmichev_dima Semiexpress (JOI17_semiexpress) C++14
100 / 100
 23 ms 1000 KB 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
#include <cassert>
#include <cmath>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <cstdlib>

using namespace std;

#define INF 1e+9
#define mp make_pair
#define pb push_back
#define fi first
#define fs first
#define se second
#define i64 long long
#define li long long
#define lint long long
#define pii pair<int, int>
#define vi vector<int>

#define forn(i, n) for (int i = 0; i < (int)n; i++)
#define fore(i, b, e) for (int i = (int)b; i <= (int)e; i++)

int main() {
#ifdef LOCAL
    freopen("inp", "r", stdin);
    //freopen("outp", "w", stdout);
#else
    // freopen(TASKNAME ".in", "r", stdin);
    // freopen(TASKNAME ".out", "w", stdout);
#endif
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    i64 A, B, C, T;
    cin >> A >> B >> C >> T;
    vi exp(m);
    forn(i, m)
        scanf("%d", &exp[i]);
    int ans = -1;
    vi next(m);
    forn(i, m - 1) {
        i64 base_time = B * (exp[i] - 1);
        if (base_time > T) {
            next[i] = -1;
            continue;
        }
        //base_time + x * A <= T
        i64 x = (T - base_time) / A;
      //  cout << "base_time =" << base_time << " x = " << x << endl;
        if (x >= exp[i + 1] - exp[i]) {
             next[i] = -1;
             ans += exp[i + 1] - exp[i];
             continue;
        }
        next[i] = exp[i] + x + 1;
      //  printf("start next[%d] = %d\n", i, next[i]);
        ans += next[i] - exp[i];
    }
    if (B * (exp[m - 1] - 1) <= T)
        ans++;
   // cout << "start ans = " << ans << endl;
    forn(iter, k - m) {
       // printf("\n==============\n");
        pii best = {-1, -1};
        forn(i, m - 1) {
            if (next[i] == -1)
                continue;
            i64 base_time = B * (exp[i] - 1) + C * (next[i] - exp[i]);
            if (base_time > T) {
                next[i] = -1;
                continue;
            }
            //printf("i = %d base_time = %lld\n", i, base_time);
            //base_time + x * A <= T
            //x * A <= T - base_time
            //x <= (T - base_time) / A
            i64 x = min((T - base_time) / A, (i64)exp[i + 1] - next[i] - 1);
            //printf("iter = %d i = %d\n", iter, i);
            //cout << "x = " << x << endl;
            pii nnew = {x, i};
            best = max(best, nnew);
        }
        if (best.fi == -1)
            break;
        ans += best.fi + 1;
        int i = best.se;
        next[i] += best.fi + 1;
        if (next[i] >= exp[i + 1]) {
            next[i] = -1;
        } else {
            i64 base_time = B * (exp[i] - 1) + C * (next[i] - exp[i]);
            if (base_time > T)
                next[i] = -1;
        }
      //  printf("added i = %d next[i] = %d\n", i, next[i]);
    }
    printf("%d", ans);
}

Compilation message

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &exp[i]);
         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 2 ms 548 KB Output is correct
5 Correct 2 ms 548 KB Output is correct
6 Correct 2 ms 644 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Correct 2 ms 752 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 2 ms 548 KB Output is correct
5 Correct 2 ms 548 KB Output is correct
6 Correct 2 ms 644 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Correct 2 ms 752 KB Output is correct
9 Correct 2 ms 764 KB Output is correct
10 Correct 2 ms 764 KB Output is correct
11 Correct 2 ms 764 KB Output is correct
12 Correct 2 ms 764 KB Output is correct
13 Correct 2 ms 764 KB Output is correct
14 Correct 2 ms 764 KB Output is correct
15 Correct 2 ms 764 KB Output is correct
16 Correct 2 ms 764 KB Output is correct
17 Correct 2 ms 764 KB Output is correct
18 Correct 2 ms 764 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 2 ms 548 KB Output is correct
5 Correct 2 ms 548 KB Output is correct
6 Correct 2 ms 644 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Correct 2 ms 752 KB Output is correct
9 Correct 2 ms 764 KB Output is correct
10 Correct 2 ms 764 KB Output is correct
11 Correct 2 ms 764 KB Output is correct
12 Correct 2 ms 764 KB Output is correct
13 Correct 2 ms 764 KB Output is correct
14 Correct 2 ms 764 KB Output is correct
15 Correct 2 ms 764 KB Output is correct
16 Correct 2 ms 764 KB Output is correct
17 Correct 2 ms 764 KB Output is correct
18 Correct 2 ms 764 KB Output is correct
19 Correct 2 ms 804 KB Output is correct
20 Correct 2 ms 820 KB Output is correct
21 Correct 2 ms 820 KB Output is correct
22 Correct 3 ms 868 KB Output is correct
23 Correct 23 ms 900 KB Output is correct
24 Correct 2 ms 936 KB Output is correct
25 Correct 2 ms 952 KB Output is correct
26 Correct 2 ms 964 KB Output is correct
27 Correct 3 ms 984 KB Output is correct
28 Correct 2 ms 1000 KB Output is correct
29 Correct 7 ms 1000 KB Output is correct
30 Correct 5 ms 1000 KB Output is correct