Submission #68425

#	Time	Username	Problem	Language	Result	Execution time	Memory
68425		BThero	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	28 ms	980 KiB

semiexpress

// Why I am so dumb? :c
#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

using namespace std;

typedef long long ll;

const int MAXN = (int)3e3 + 5;

int reach[MAXN];

ll dist[MAXN];

int arr[MAXN];

int n, m, k;	

ll a, b, c;

int ans;

ll lim;

void solve() {                   
    scanf("%d %d %d", &n, &m, &k);
    scanf("%lld %lld %lld", &a, &b, &c);
    scanf("%lld", &lim);

    for (int i = 1; i <= m; ++i) {
    	scanf("%d", &arr[i]);
    }

	for (int i = 1; i <= m; ++i) {
		dist[i] = (arr[i] - 1) * b;		

		if (dist[i] > lim) {
			continue;
		}

		if (i > 1) {
			++ans;
		}

		reach[i] = min(arr[i + 1] - 1ll, (lim - dist[i]) / a + arr[i]);         
	}

	for (int i = 1; i <= k - m; ++i) {
		pair<int, int> mx = mp(-1, -1);

		for (int j = 1; j < m; ++j) {
			if (dist[j] > lim) {
				continue;
			}

			// try putting express at reach[j] + 1
			int id = reach[j] + 1;

			ll ext = (id - arr[j]) * c;

			if (dist[j] + ext > lim) {
				continue;
			}

			int x = min(arr[j + 1] - 1ll, (lim - dist[j] - ext) / a + id);            
			mx = max(mx, mp(x - reach[j], j));
		}

		if (mx.se == -1) {
			break;
		}

		reach[mx.se] += mx.fi;	
	}

	for (int i = 1; i < m; ++i) {
		if (dist[i] > lim) {
			continue;
		}

		ans += (reach[i] - arr[i]);
	}

	printf("%d\n", ans);
}

int main() {    
    int tt = 1;

    while (tt--) {
        solve();
    }

    return 0;
}

Compilation message (stderr)

semiexpress.cpp: In function 'void solve()':
semiexpress.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld %lld", &a, &b, &c);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &lim);
     ~~~~~^~~~~~~~~~~~~~
semiexpress.cpp:38:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d", &arr[i]);
      ~~~~~^~~~~~~~~~~~~~~

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