oj.uz

Submission #140840

# Submission time Handle Problem Language Result Execution time Memory
140840 2019-08-05T15:06:38 Z DrumpfTheGodEmperor Semiexpress (JOI17_semiexpress) C++14
100 / 100
 993 ms 141904 KB 
#include <bits/stdc++.h>
#define int long long
#define bp __builtin_popcountll
#define pb push_back
#define in(s) freopen(s, "r", stdin);
#define out(s) freopen(s, "w", stdout);
#define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\
		freopen((string(s) + "." + end2).c_str(), "w", stdout);
#define fi first
#define se second
#define bw(i, r, l) for (int i = r - 1; i >= l; i--)
#define fw(i, l, r) for (int i = l; i < r; i++)
#define fa(i, x) for (auto i: x)
using namespace std;
const int mod = 1e9 + 7, inf = 1061109567;
const long long infll = 4557430888798830399;
const int N = 3005;
int n, m, k, a, b, c, t, s[N], mxStations[N][N], dp[N][N];
signed main() {
	#ifdef BLU
	in("blu.inp");
	#endif
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m >> k >> a >> b >> c >> t;
	k -= m;
	memset(mxStations, 0, sizeof mxStations);
	fw (i, 0, m) cin >> s[i];
	fw (i, 0, m) {
		int leftBound = s[i], rightBound = n;
		if (i < m - 1) rightBound = s[i + 1] - 1;
		//mxStations[i][j]: Maximum stations between the bounds if j stations are used.
		//Greedily place a station at minimum station that can't be reached.
		int remainingTime = t - b * (s[i] - 1);
		if (remainingTime < 0) break;
		int curPos = 1;
		fw (j, 0, k + 1) {
			int remaining = remainingTime - (curPos - 1) * c;
			if (remaining < 0) break;
			curPos = min(curPos + remaining / a, rightBound - leftBound + 1);
			mxStations[i][j] = curPos;
			curPos++;
//			cout << "Place station " << j + 1 << " at pos " << leftBound + curPos - 1 << "\n";
//			cout << "mxStations[" << i << "][" << j << "] = " << mxStations[i][j] << "\n";
		}
		if (i == 0) {
			fw (j, 0, k + 1) mxStations[i][j]--; //Not including 1.
		}
	}
	memset(dp, 0, sizeof dp);
	fw (i, 0, m) fw (j, 0, k + 1) {
		fw (l, 0, j + 1) {
			int lst = i ? dp[i - 1][j - l] : 0;
			dp[i][j] = max(dp[i][j], lst + mxStations[i][l]);
		}
	}
	cout << dp[m - 1][k];
	return 0;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 141816 KB Output is correct
2 Correct 118 ms 141684 KB Output is correct
3 Correct 118 ms 141728 KB Output is correct
4 Correct 119 ms 141688 KB Output is correct
5 Correct 117 ms 141688 KB Output is correct
6 Correct 118 ms 141688 KB Output is correct
7 Correct 117 ms 141664 KB Output is correct
8 Correct 117 ms 141732 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 141816 KB Output is correct
2 Correct 118 ms 141684 KB Output is correct
3 Correct 118 ms 141728 KB Output is correct
4 Correct 119 ms 141688 KB Output is correct
5 Correct 117 ms 141688 KB Output is correct
6 Correct 118 ms 141688 KB Output is correct
7 Correct 117 ms 141664 KB Output is correct
8 Correct 117 ms 141732 KB Output is correct
9 Correct 117 ms 141840 KB Output is correct
10 Correct 118 ms 141688 KB Output is correct
11 Correct 118 ms 141636 KB Output is correct
12 Correct 117 ms 141688 KB Output is correct
13 Correct 119 ms 141688 KB Output is correct
14 Correct 116 ms 141688 KB Output is correct
15 Correct 117 ms 141744 KB Output is correct
16 Correct 117 ms 141688 KB Output is correct
17 Correct 118 ms 141836 KB Output is correct
18 Correct 119 ms 141688 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 141816 KB Output is correct
2 Correct 118 ms 141684 KB Output is correct
3 Correct 118 ms 141728 KB Output is correct
4 Correct 119 ms 141688 KB Output is correct
5 Correct 117 ms 141688 KB Output is correct
6 Correct 118 ms 141688 KB Output is correct
7 Correct 117 ms 141664 KB Output is correct
8 Correct 117 ms 141732 KB Output is correct
9 Correct 117 ms 141840 KB Output is correct
10 Correct 118 ms 141688 KB Output is correct
11 Correct 118 ms 141636 KB Output is correct
12 Correct 117 ms 141688 KB Output is correct
13 Correct 119 ms 141688 KB Output is correct
14 Correct 116 ms 141688 KB Output is correct
15 Correct 117 ms 141744 KB Output is correct
16 Correct 117 ms 141688 KB Output is correct
17 Correct 118 ms 141836 KB Output is correct
18 Correct 119 ms 141688 KB Output is correct
19 Correct 292 ms 141904 KB Output is correct
20 Correct 993 ms 141816 KB Output is correct
21 Correct 117 ms 141688 KB Output is correct
22 Correct 136 ms 141732 KB Output is correct
23 Correct 550 ms 141688 KB Output is correct
24 Correct 118 ms 141688 KB Output is correct
25 Correct 119 ms 141732 KB Output is correct
26 Correct 132 ms 141728 KB Output is correct
27 Correct 119 ms 141820 KB Output is correct
28 Correct 117 ms 141672 KB Output is correct
29 Correct 234 ms 141688 KB Output is correct
30 Correct 331 ms 141836 KB Output is correct