Submission #242488

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
242488	2020-06-27T20:30:58 Z	MatesV13	Segway (COI19_segway)	C++11	55 / 100	49 ms	1536 KB

segway

#include <bits/stdc++.h>
using namespace std;
long long n, a[20005], b[20005], c[20005];
long long m, x, seg[305], dp[305][305], poz[305], ubrz[305];
long long ans[20005], nekoime[20005];
long long ubrzaj (int pozicija, int trenutak){
	int ret=0;
	for (int i=0; i<n; i++)
		if (dp[i][pozicija] and dp[i][pozicija]<trenutak) ret++;
	return (ret%20);
}
int main (){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n; for (int i=0; i<n; i++) cin >> a[i] >> b[i] >> c[i];
cin >> m; for (int i=0; i<m; i++){cin >> x; seg[x]++;} 
if (m!=1){
for (long long vrijeme=1; vrijeme<15005; vrijeme++){
	for (int i=0; i<n; i++){
		if (poz[i]>=300) continue;
		if (ubrz[i]){
			dp[i][poz[i]+1] = dp[i][poz[i]]+1;
			ubrz[i]--; poz[i]++;
			if (!ubrz[i] and seg[poz[i]]) 
				ubrz[i] = ubrzaj(poz[i], vrijeme);
		}
		else {
			if (poz[i]<100){
				if (vrijeme - dp[i][poz[i]] == a[i]){
					dp[i][poz[i]+1]=vrijeme;
					poz[i]++; 
					if (!ubrz[i] and seg[poz[i]]) 
						ubrz[i] = ubrzaj(poz[i], vrijeme);
				}
			}
			else if (poz[i]<200){
				if (vrijeme - dp[i][poz[i]] == b[i]){
					dp[i][poz[i]+1]=vrijeme;
					poz[i]++; 
					if (!ubrz[i] and seg[poz[i]]) 
						ubrz[i] = ubrzaj(poz[i], vrijeme);
				}
			}
			else {
				if (vrijeme - dp[i][poz[i]] == c[i]){
					dp[i][poz[i]+1]=vrijeme;
					poz[i]++; 
					if (!ubrz[i] and seg[poz[i]]) 
						ubrz[i] = ubrzaj(poz[i], vrijeme);
				}
			}
		}
	}
}

for (int i=0; i<n; i++) ans[i] = dp[i][300];
}
else {
	vector<pair<int, int> > time_person;
	for (int i=0; i<n; i++){
		if (x<=100) {
			ans[i] = x*a[i];
			time_person.push_back(make_pair(ans[i], i));
		}
		else {
			ans[i]=a[i]*100;
			if (x<=200){
				ans[i] += (x-100)*b[i];
				time_person.push_back(make_pair(ans[i], i));
			}
			else {
				ans[i]+=b[i]*100;
				ans[i]+=(x-200)*c[i];
				time_person.push_back(make_pair(ans[i], i));
			}
		}
	}
	sort(time_person.begin(), time_person.end());
	for (int i=0; i<n; i++){
		if (i and time_person[i].first == time_person[i-1].first){
			nekoime[i]=nekoime[i-1];
		} else nekoime[i]=i; nekoime[i]%=20;
		int idx = time_person[i].second;
		if (nekoime[i]+x>300) ans[idx] += (300-x);
		else {
			ans[idx]+=nekoime[i];
			x+=nekoime[i];
			if (x<=100)
				ans[idx] += (100-x)*a[idx] + 100*b[idx] + 100*c[idx];
			else if (x<=200)
				ans[idx] += (200-x)*b[idx] + 100*c[idx];
			else 
				ans[idx] += (300-x)*c[idx];
			x-=nekoime[i];
		}
	}
}
for (int i=0; i<n; i++) cout << ans[i] << endl;
return 0;
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	6 ms	384 KB	Output is correct
4	Correct	11 ms	512 KB	Output is correct
5	Correct	49 ms	1536 KB	Output is correct

Subtask #2

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	6 ms	512 KB	Output is correct
6	Correct	6 ms	512 KB	Output is correct
7	Correct	7 ms	640 KB	Output is correct
8	Correct	11 ms	896 KB	Output is correct
9	Correct	13 ms	896 KB	Output is correct
10	Correct	16 ms	1152 KB	Output is correct
11	Correct	14 ms	1024 KB	Output is correct

Subtask #3

0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	6 ms	384 KB	Output is correct
4	Correct	11 ms	512 KB	Output is correct
5	Correct	49 ms	1536 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	6 ms	512 KB	Output is correct
11	Correct	6 ms	512 KB	Output is correct
12	Correct	7 ms	640 KB	Output is correct
13	Correct	11 ms	896 KB	Output is correct
14	Correct	13 ms	896 KB	Output is correct
15	Correct	16 ms	1152 KB	Output is correct
16	Correct	14 ms	1024 KB	Output is correct
17	Runtime error	6 ms	768 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
18	Halted	0 ms	0 KB	-