oj.uz

Submission #34051

# Submission time Handle Problem Language Result Execution time Memory
34051 2017-11-06T16:00:22 Z DoanPhuDuc Semiexpress (JOI17_semiexpress) C++
100 / 100
 46 ms 108200 KB 
#include <bits/stdc++.h>

#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n)  { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }
#define BitCount(x) __builtin_popcount(x)

using namespace std;

typedef long long LL;

const int N = 3e3 + 10;

int n, m, k, PA, PB, PC;
int a[N];
int f[N][N], pos[N][N], dp[N][N];

LL t;

void Compute(int p, int l, int r, int u, int v) {
    if (l > r) return;
    int m = (l + r) >> 1;
    int x = max(u, 0), y = min(m, v);
    int best = -1;
    FOR(j, x, y)
        if (dp[p][m] < dp[p - 1][j] + f[p][m - j] + 1) {
            dp[p][m] = dp[p - 1][j] + f[p][m - j] + 1;
            best = j;
        }
    Compute(p, l, m - 1, u, best);
    Compute(p, m + 1, r, best, v);
}

int main() {
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // LOCAL
    scanf("%d%d%d", &n, &m, &k); k -= m;
    scanf("%d%d%d", &PA, &PB, &PC);
    scanf("%lld", &t);
    FOR(i, 1, m) scanf("%d", &a[i]);
   // sort(a + 1, a + m + 1); m = unique(a + 1, a + m + 1) - a - 1;
    FOR(i, 1, m - 1) {
        LL restTime = t - (LL)PB * (a[i] - a[1]);
        if (restTime <= 0) break;
        int x = a[i];
        FOR(j, 0, k) {
            if (restTime <= 0) {
                int v = f[i][j - 1] + (restTime == 0);
                FOR(p, j, k) f[i][p] = v;
                break;
            }
            int y = (restTime + (LL)x * PA) / PA;
            if (y >= a[i + 1] - 1) {
                FOR(p, j, k) f[i][p] = a[i + 1] - 1 - a[i];
                break;
            }
            f[i][j] = y - a[i];
            restTime -= (LL)(y + 1 - x) * PC;
            x = y + 1;
        }
    }
    FOR(i, 1, m - 1) {
        LL restTime = t - (LL)PB * (a[i] - a[1]);
        if (restTime <= 0) {
            printf("%d", dp[i - 1][k] + (restTime == 0) - 1);
            return 0;
        }
        Compute(i, 0, k, 0, k);

    }
  /*  FOR(i, 1, m - 1) {
        LL restTime = t - (LL)PB * (a[i] - a[1]);
        if (restTime <= 0) {
            printf("%d", dp[i - 1][k] + (restTime == 0) - 1);
            return 0;
        }
        FOR(j, 0, k)
            FOR(x, 0, j)
                if (dp[i - 1][j - x] + f[i][x] + 1 > dp[i][j]) {
                    dp[i][j] = dp[i - 1][j - x] + f[i][x] + 1;
                    pos[i][j] = j - x;
                }
        FOR(j, 0, k) printf("%d ", pos[i][j]);
        putchar('\n');
    }*/
    printf("%d\n", dp[m - 1][k] + (t - (LL)PB * (a[m] - a[1]) >= 0) - 1);
    return 0;
}

Compilation message

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:42:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &k); k -= m;
                                ^
semiexpress.cpp:43:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &PA, &PB, &PC);
                                   ^
semiexpress.cpp:44:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &t);
                      ^
semiexpress.cpp:45:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     FOR(i, 1, m) scanf("%d", &a[i]);
                                    ^

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 108200 KB Output is correct
2 Correct 0 ms 108200 KB Output is correct
3 Correct 0 ms 108200 KB Output is correct
4 Correct 0 ms 108200 KB Output is correct
5 Correct 0 ms 108200 KB Output is correct
6 Correct 0 ms 108200 KB Output is correct
7 Correct 0 ms 108200 KB Output is correct
8 Correct 0 ms 108200 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 108200 KB Output is correct
2 Correct 0 ms 108200 KB Output is correct
3 Correct 0 ms 108200 KB Output is correct
4 Correct 0 ms 108200 KB Output is correct
5 Correct 0 ms 108200 KB Output is correct
6 Correct 0 ms 108200 KB Output is correct
7 Correct 0 ms 108200 KB Output is correct
8 Correct 0 ms 108200 KB Output is correct
9 Correct 0 ms 108200 KB Output is correct
10 Correct 0 ms 108200 KB Output is correct
11 Correct 0 ms 108200 KB Output is correct
12 Correct 0 ms 108200 KB Output is correct
13 Correct 0 ms 108200 KB Output is correct
14 Correct 0 ms 108200 KB Output is correct
15 Correct 0 ms 108200 KB Output is correct
16 Correct 0 ms 108200 KB Output is correct
17 Correct 0 ms 108200 KB Output is correct
18 Correct 0 ms 108200 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 108200 KB Output is correct
2 Correct 0 ms 108200 KB Output is correct
3 Correct 0 ms 108200 KB Output is correct
4 Correct 0 ms 108200 KB Output is correct
5 Correct 0 ms 108200 KB Output is correct
6 Correct 0 ms 108200 KB Output is correct
7 Correct 0 ms 108200 KB Output is correct
8 Correct 0 ms 108200 KB Output is correct
9 Correct 0 ms 108200 KB Output is correct
10 Correct 0 ms 108200 KB Output is correct
11 Correct 0 ms 108200 KB Output is correct
12 Correct 0 ms 108200 KB Output is correct
13 Correct 0 ms 108200 KB Output is correct
14 Correct 0 ms 108200 KB Output is correct
15 Correct 0 ms 108200 KB Output is correct
16 Correct 0 ms 108200 KB Output is correct
17 Correct 0 ms 108200 KB Output is correct
18 Correct 0 ms 108200 KB Output is correct
19 Correct 3 ms 108200 KB Output is correct
20 Correct 3 ms 108200 KB Output is correct
21 Correct 0 ms 108200 KB Output is correct
22 Correct 0 ms 108200 KB Output is correct
23 Correct 46 ms 108200 KB Output is correct
24 Correct 3 ms 108200 KB Output is correct
25 Correct 0 ms 108200 KB Output is correct
26 Correct 6 ms 108200 KB Output is correct
27 Correct 3 ms 108200 KB Output is correct
28 Correct 3 ms 108200 KB Output is correct
29 Correct 9 ms 108200 KB Output is correct
30 Correct 9 ms 108200 KB Output is correct