Submission #173454

#	Time	Username	Problem	Language	Result	Execution time	Memory
173454		dennisstar	Semiexpress (JOI17_semiexpress)	C++11	48 / 100	2 ms	424 KiB

semiexpress

#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
#define all(V) ((V).begin()), ((V).end())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;
typedef vector<ll> vlm;

ll N, M, K, Loc, Ex, Sem, T;
ll S[3010], ans;
priority_queue<pair<ll, pll> > pq;

int main() {
	scanf("%lld %lld %lld %lld %lld %lld %lld", &N, &M, &K, &Loc, &Ex, &Sem, &T);
	for (int i=1; i<=M; i++) scanf("%lld", &S[i]);
	S[M+1]=N+1;
	K-=M;
	ll LT;
	for (int i=1; i<=M; i++) {
		if ((S[i]-1)*Ex<=T) {
			LT=T-(S[i]-1)*Ex;
			ans+=min(S[i+1]-1, S[i]+LT/Loc)-S[i]+1;
			if (S[i]+LT/Loc < S[i+1]-1 && (LT-Sem*(LT/Loc+1))>=0 ) { //추가개수, 최대개수, 잔여시간
				//시작점 : S[i]+(LT/loc)+1
				pq.push({ min(S[i+1]-1-(S[i]+LT/Loc), 1+(LT-Sem*(LT/Loc+1))/Loc) , make_pair(S[i+1]-1-(S[i]+LT/Loc), (LT-Sem*(LT/Loc+1))) });
			}
		}
	}
	while (K--&&!pq.empty()) {
		auto pi=pq.top(); pq.pop();
		ans+=pi.fi;
		if (pi.se.fi>pi.fi && pi.se.se>=(Sem+1)*pi.fi) pq.push({ min((pi.se.se-Sem*(pi.fi+1))/Loc+1, pi.se.fi-pi.fi) , make_pair(pi.se.fi-pi.fi, pi.se.se-(Sem+1)*pi.fi) });
	}
	printf("%lld\n", ans-1);
	return 0;
}

Compilation message (stderr)

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld %lld %lld %lld %lld", &N, &M, &K, &Loc, &Ex, &Sem, &T);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:20:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=1; i<=M; i++) scanf("%lld", &S[i]);
                           ~~~~~^~~~~~~~~~~~~~~

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