oj.uz

Submission #34050

# Submission time Handle Problem Language Result Execution time Memory
34050 2017-11-06T15:47:59 Z DoanPhuDuc Semiexpress (JOI17_semiexpress) C++
100 / 100
 499 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;

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;
        }
        FOR(j, 0, k)
            FOR(x, 0, j) dp[i][j] = max(dp[i][j], dp[i - 1][j - x] + f[i][x] + 1);
    }
    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:28: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:29: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:30:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &t);
                      ^
semiexpress.cpp:31: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 33 ms 108200 KB Output is correct
20 Correct 163 ms 108200 KB Output is correct
21 Correct 0 ms 108200 KB Output is correct
22 Correct 3 ms 108200 KB Output is correct
23 Correct 499 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 9 ms 108200 KB Output is correct
28 Correct 0 ms 108200 KB Output is correct
29 Correct 139 ms 108200 KB Output is correct
30 Correct 263 ms 108200 KB Output is correct