Submission #68418

#	Time	Username	Problem	Language	Result	Execution time	Memory
68418		BThero	Semiexpress (JOI17_semiexpress)	C++17	48 / 100	1073 ms	692 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)3e2 + 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] = arr[i];

		for (int x = arr[i] + 1; x < arr[i + 1]; ++x) {
			if (dist[i] + (x - arr[i]) * a <= lim) {
				reach[i] = x;
			}
		} 
	}

	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 cnt = 0;
			int id = reach[j] + 1;

			for (int x = id; x < arr[j + 1]; ++x) {
				if (dist[j] + (id - arr[j]) * c + (x - id) * a <= lim) {
					++cnt;
				}		
			}

			mx = max(mx, mp(cnt, 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: 0 / 52