Submission #1024208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024208		phong	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	51 ms	4952 KiB

semiexpress

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

#define ll long long
#define int long long
const int nmax = 2e5 + 5;
const int lg = 18;
const int base = 311;
const int M = 5e6;
const ll oo = 1e9;
const int mod = 987654321;
#define fi first
#define se second
#define endl "\n"
#define pii pair<ll, int>

using namespace std;

int n, m, k, A, B, C, T;
int a[nmax], pos[nmax], one[nmax];
ll dp[nmax];
void ckmin(ll &a, ll b){
    a = min(a, b);
}
main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> n >> m >> k >> A >> B >> C >> T;
    for(int i = 1; i <= m; ++i) cin >> a[i], pos[i] = a[i - 1] + 1;
    k = k - m;
    memset(dp, 0x3f, sizeof dp);
    dp[1] = 0;
    ll ans = 0;
    for(int i = 2; i <= m; ++i){
        ckmin(dp[i], dp[i - 1] + (a[i] - a[i - 1]) * B);
        one[i] = a[i - 1];
        if(dp[i] <= T) ans++;
    }
    for(int e = 0; e <= k; ++e){
        int ma = 0, idx = -1, tmp = -1;
        for(int i = 2; i <= m; ++i){
            if(dp[i - 1] > T) break;
            int l = one[i] + 1, r = a[i] - 1, kq = -1;
            if(e == 0){
                while(l <= r){
                    int mid = r + l >> 1;
                    if(dp[i - 1] + (mid - a[i - 1]) * A <= T){
                        kq = mid;
                        l = mid + 1;
                    }
                    else r = mid - 1;
                }
                if(kq == -1) one[i] = a[i - 1];
                else one[i] = kq;
//                cout << kq - a[i - 1] << ' ';
                ans += max(0ll, kq - a[i - 1]);
            }
            else{
                int pepe = one[i] + 1;
                 while(l <= r){
                    int mid = r + l >> 1;
                    int x = (pepe - a[i - 1]) * C;
                    int y = (mid - pepe) * A;
                    if(dp[i - 1] + x + y <= T){
                        kq = mid;
                        l = mid + 1;
                    }
                    else r = mid - 1;
                }
                if(ma < kq - one[i]){
                   ma = kq - one[i];
                   idx = i;
                   tmp = kq;
                }
//                if(kq == -1) continue;
//                cout << i << ' ' << pepe << endl;
//                cout << pepe - a[i - 1] << ' ';
            }
        }
        if(e == 0) continue;
        if(!ma) break;
        one[idx] = tmp;
        ans += ma;
    }
    cout << ans;
}
/*
7 3 4
11 4 5
15
1 3 7
4

*/

Compilation message (stderr)

semiexpress.cpp:27:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   27 | main(){
      | ^~~~
semiexpress.cpp: In function 'int main()':
semiexpress.cpp:50:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |                     int mid = r + l >> 1;
      |                               ~~^~~
semiexpress.cpp:65:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |                     int mid = r + l >> 1;
      |                               ~~^~~

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52