oj.uz

Submission #68425

# Submission time Handle Problem Language Result Execution time Memory
68425 2018-08-17T06:24:21 Z BThero Semiexpress (JOI17_semiexpress) C++17
100 / 100
 28 ms 980 KB 
// 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

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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 3 ms 572 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 2 ms 620 KB Output is correct
12 Correct 2 ms 620 KB Output is correct
13 Correct 3 ms 620 KB Output is correct
14 Correct 3 ms 620 KB Output is correct
15 Correct 3 ms 620 KB Output is correct
16 Correct 2 ms 624 KB Output is correct
17 Correct 2 ms 624 KB Output is correct
18 Correct 2 ms 624 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 3 ms 572 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 2 ms 620 KB Output is correct
12 Correct 2 ms 620 KB Output is correct
13 Correct 3 ms 620 KB Output is correct
14 Correct 3 ms 620 KB Output is correct
15 Correct 3 ms 620 KB Output is correct
16 Correct 2 ms 624 KB Output is correct
17 Correct 2 ms 624 KB Output is correct
18 Correct 2 ms 624 KB Output is correct
19 Correct 7 ms 624 KB Output is correct
20 Correct 8 ms 732 KB Output is correct
21 Correct 4 ms 796 KB Output is correct
22 Correct 4 ms 796 KB Output is correct
23 Correct 28 ms 876 KB Output is correct
24 Correct 4 ms 876 KB Output is correct
25 Correct 3 ms 920 KB Output is correct
26 Correct 3 ms 920 KB Output is correct
27 Correct 4 ms 920 KB Output is correct
28 Correct 4 ms 980 KB Output is correct
29 Correct 9 ms 980 KB Output is correct
30 Correct 6 ms 980 KB Output is correct