oj.uz

Submission #593955

# Submission time Handle Problem Language Result Execution time Memory
593955 2022-07-11T18:04:18 Z VasLemmy Semiexpress (JOI17_semiexpress) C++17
100 / 100
 8 ms 408 KB 
/// slava sovet·skomu soyuzu
#include <bits/stdc++.h>
using namespace std;
using db = long double;

#define int long long
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back

const int mod =  1000000007;
const int maxN = 200005;
const int base = 31;
const ll infty = 1000000000000000000;

int n,m,k;
int a,b,c;
int t;
int s[maxN];
int lst[3003];


void read()
{
    cin >> n >> m >> k;
    cin >> a >> b >> c;
    cin >> t;
    for(int i = 1; i <= m; i++)
    {
        cin >> s[i];
    }
    int res = 0;
    s[m+1] = n + 1;
    for(int i = 1; i <= m; i++)
    {
        if(t - (s[i] - 1) * b < 0)
        {
            lst[i] = -1;
            continue;
        }
        int lim = (t - (s[i] - 1) * b) / a + s[i];

        lim = min(lim,s[i+1]-1);
        lst[i] = lim;
        res += lim - s[i] + 1;
    }

    /*for(int i = 1;i <= m;i++)
    {
        cout << lst[i] <<'\n';
    }
    return;*/

    for(int j = 1;j <= k - m;j++)
    {
        int more = 0;
        int id = -1;
        for(int i = 1;i < m;i++)
        {
            if(lst[i] == -1) continue;
            if(lst[i] + 1 == s[i+1]) continue;
            if((s[i] - 1) * b + ((lst[i] + 1) - s[i]) * c > t) continue;
            int nxt_semi = lst[i] + 1;
            int lim = (t - ((s[i] - 1) * b + (nxt_semi - s[i]) * c)) / a + nxt_semi;
            lim = min(lim,s[i+1]-1);
            if(lim - lst[i] > more)
            {
                more = lim - lst[i];
                id = i;
            }
        }
        if(more > 0)
        {
            res += more;
            lst[id] += more;
        }
    }
    cout << res - 1;
}

void sol()
{

}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("test.inp","r",stdin);
    int tests;
    //cin >> tests;
    tests = 1;
    while (tests--)
    {
        read();
        sol();
    }
    return 0;
}

Subtask #1
18.0 / 18.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
52.0 / 52.0

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