oj.uz

Submission #670464

# Submission time Handle Problem Language Result Execution time Memory
670464 2022-12-09T07:47:52 Z fatemetmhr Semiexpress (JOI17_semiexpress) C++17
48 / 100
 2 ms 400 KB 
// ~ Be Name Khoda ~

#include<bits/stdc++.h>
//#pragma GCC optimize ("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  1e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  1e18;

ll dp[2][maxn5], s[maxn5], have[maxn5];

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);

    int n, m, k; cin >> n >> m >> k;
    ll a, b, c, t; cin >> a >> b >> c >> t;

    for(int i = 0; i < m; i++)
        cin >> s[i];
    k -= m;
    ll ans = 0;
    for(int i = 0; i < m - 1; i++){
        ll pos = s[i], tim = (s[i] - 1) * b, done = 0;
        int mx = -1;
        for(int j = 0; j <= k; j++){
            dp[i&1][j] = have[j] = 0;
            if(tim > t || pos == s[i + 1])
                continue;
            have[j] = done + min(s[i + 1] - pos, (t - tim) / a + 1);
            ll tt = tim;
            tim += c * min(s[i + 1] - pos, (t - tim) / a + 1);
            pos = min(s[i + 1], pos + (t - tt) / a + 1);
            mx = j;
            done = have[j];
        }
        if(mx == -1)
            break;

        for(int j = 0; j <= k; j++){
            if(j + mx <= k){
                dp[i&1][j + mx] = max(dp[i&1][j + mx], dp[(i&1)^1][j] + have[mx]);
            }
            if(mx && j + mx - 1 <= k)
                dp[i&1][j + mx - 1] = max(dp[i&1][j + mx - 1], dp[(i&1)^1][j] + have[mx - 1]);
            if(k - j <= mx)
                dp[i&1][k] = max(dp[i&1][k], dp[(i&1)^1][j] + have[k - j]);
        }
        for(int j = 0; j <= k; j++){
            ans = max(ans, dp[i&1][j]);
        }
    }
    if((n - 1) * b <= t)
        ans++;
    cout << ans - 1 << endl;
}

/*
Why so fast...? 
Hold on...
Hold your breath...
Need anything else?

Nein, Kein Problem...
Das Leben war schon immer so grausam :)
*/

Subtask #1
18.0 / 18.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 2 ms 400 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Incorrect 1 ms 340 KB Output isn't correct
23 Halted 0 ms 0 KB -