Submission #1116210

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116210		staszic_ojuz	Semiexpress (JOI17_semiexpress)	C++17	18 / 100	1 ms	504 KiB

semiexpress

#include <bits/stdc++.h>
using namespace std;
using ll=int64_t;
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll ilosc_stacji,ilosc_express,ilosc_semi;
	ll czas_local,czas_express,czas_semi;
	ll maks_czas,gdzie_pociag_exp;
	cin >> ilosc_stacji >> ilosc_express >> ilosc_semi;
	cin >> czas_local >> czas_express >> czas_semi;
	cin >> maks_czas;
	vector<ll>pozycje_exp;
	for(int i=0;i<ilosc_express;++i){
		cin >> gdzie_pociag_exp;
		pozycje_exp.push_back(gdzie_pociag_exp);
	}
	ilosc_semi-=ilosc_express;
	vector<ll>dp(ilosc_stacji);
	vector<bool>semi(ilosc_stacji);
	semi[0]=1;
	for(int i=1;i<ilosc_express;++i){
		dp[pozycje_exp[i]-1]=dp[pozycje_exp[i-1]-1]+(pozycje_exp[i]-pozycje_exp[i-1])*czas_express;
		semi[pozycje_exp[i]-1]=1;
	}
	for(int i=1;i<ilosc_stacji;++i){
		if(dp[i]!=0)
			dp[i]=min(dp[i-1]+czas_local,dp[i]);
		else
			dp[i]=dp[i-1]+czas_local;
	}

	ll index;	
	
	for(int i=0;i<ilosc_stacji;++i){
		if(semi[i]) index=i;
		if(dp[i]>maks_czas){
			if(dp[index]+czas_semi*(i-index)<=maks_czas && ilosc_semi >0 ){
				dp[i]=dp[index]+czas_semi*(i-index);
				semi[i]=1;
				index=i;
				ilosc_semi--;
				for(int j=index+1;semi[j]!=1;++j){
					if(dp[j-1]+czas_local>maks_czas) break;
					dp[j]=min(dp[j-1]+czas_local,dp[j]);
				}
				
			}
		}
	}
	
	ll suma=0;
	for(int i=1;i<ilosc_stacji;++i){
		if(dp[i]<=maks_czas)
			suma++;
	}
	cout << suma;
	return 0;
}

Compilation message (stderr)

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:38:15: warning: 'index' may be used uninitialized in this function [-Wmaybe-uninitialized]
   38 |    if(dp[index]+czas_semi*(i-index)<=maks_czas && ilosc_semi >0 ){
      |               ^

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