Submission #1160424

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160424		qin	Semiexpress (JOI17_semiexpress)	C++20	18 / 100	0 ms	328 KiB

semiexpress

#ifndef LOCAL
#pragma GCC optimize("O3,unroll-loops")
#endif
#include <bits/stdc++.h>
#define fi first
#define se second
#define pn printf("\n")
#define ssize(x) int(x.size())
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define bitcount(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)
#define ctz(x) __builtin_ctz(x)
#define mp make_pair
//~ #define r(x) resize(x)
//~ #define rf(x, c) resize(x, c)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
#define V vector
int inf = 2e09; ll infll = 2e18; int mod = (1<<23)*119+1;
int add(int a, int b){return a+b >= mod ? a+b - mod : a+b;}
int sub(int a, int b){return a-b < 0 ? a-b + mod : a-b;}
int mul(int a, int b){return int(a * ll(b) % mod);}
int fpow(int a, ll b){
    int ret = 1;
    while(b){
        if(b & 1) ret = mul(ret, a);
        b >>= 1, a = mul(a, a);
    } return ret;
}
int inv(int a){ return fpow(a, mod-2); }
struct coeff{
    V<int> fac, invfac;
    coeff(int n){
        fac.resize(n+1), invfac.resize(n+1);
        fac[0] = 1, invfac[0] = 1;
        for(int i = 1; i <= n; ++i) fac[i] = mul(fac[i-1], i);
        invfac[n] = inv(fac[n]);
        for(int i = n-1; i; --i) invfac[i] = mul(invfac[i+1], i+1);
    }
    int get(int n, int k){
        if(n < k) return 0;
        return mul(fac[n], mul(invfac[n-k], invfac[k]));
    }
};
void answer(){
	int n, m, k; scanf("%d%d%d", &n, &m, &k);
    ll a, b, c; scanf("%lld%lld%lld", &a, &b, &c);
    ll mx; scanf("%lld", &mx);
    V<ll> t(m);
    for(ll &u : t) scanf("%lld", &u);

    auto solve = [&](ll N, ll T){ // idziemy od 1 do n
        V<ll> ret;
        ll pos = 1;
        while(T >= 0 && pos <= N && ssize(ret) <= k){
            // printf("%lld %lld\n", N, T);
            ll newpos = min(N, pos+T/a);
            ret.emplace_back(newpos);
            T -= (newpos+1-pos)*c;
            pos = newpos+1;
        }
        return ret;
    };

    V<V<ll>> res(m-1);
    for(int i = 0; i < m-1; ++i) res[i] = solve(t[i+1]-t[i], mx-(t[i]-1)*b);

    // for(V<ll> v : res){
    //     for(ll u : v) printf("%lld ", u);
    //     pn;
    // }

    auto merge = [&](V<ll> A, V<ll> B){
        for(int i = 0; i < ssize(B)-2; ++i) assert(B[i+1]-B[i] >= B[i+2]-B[i+1]);
        int l = 0, r = 0;
        V<ll> C(ssize(A)+ssize(B), 0);
        C[0] = A[0]+B[0];
        while(l < ssize(A)-1 || r < ssize(B)-1){
            if(l < ssize(A)-1 && r < ssize(B)-1){
                if(B[r+1]-B[r] < A[l+1]-A[l])
                    C[l+r+1] = C[l+r]+A[l+1]-A[l], ++l;
                else
                    C[l+r+1] = C[l+r]+B[r+1]-B[r], ++r;
            }
            else if(l < ssize(A)-1)
                C[l+r+1] = C[l+r]+A[l+1]-A[l], ++l;
            else
                C[l+r+1] = C[l+r]+B[r+1]-B[r], ++r;
        }
        if(ssize(C) > k+1) C.resize(k+1);
        return C;
    };

    k -= m;
    V<ll> dp(1, 0);
    // for(ll u : dp) printf("%lld ", u);
    // printf("\n");
    for(int l = 0; l < m-1; ++l){
        if(ssize(res[l])) dp = merge(dp, res[l]);
        // for(ll u : dp) printf("%lld ", u);
        // printf("\n");
    }

    ll result = 0;
    for(int i = 0; i <= k; ++i) result = max(result, dp[i]);
    printf("%lld\n", result+(mx/b >= n-1 ? 1 : 0)-1);
}
int main(){
		int T = 1;
		// scanf("%d", &T);
		//~ ios_base::sync_with_stdio(0); cin.tie(0); cin >> T;
		for(++T; --T; ) answer();
		return 0;
}

Compilation message (stderr)

semiexpress.cpp: In function 'void answer()':
semiexpress.cpp:53:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         int n, m, k; scanf("%d%d%d", &n, &m, &k);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:54:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     ll a, b, c; scanf("%lld%lld%lld", &a, &b, &c);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:55:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     ll mx; scanf("%lld", &mx);
      |            ~~~~~^~~~~~~~~~~~~
semiexpress.cpp:57:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     for(ll &u : t) scanf("%lld", &u);
      |                    ~~~~~^~~~~~~~~~~~

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