oj.uz

답안 #173455

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
173455 2020-01-04T07:34:11 Z dennisstar Semiexpress (JOI17_semiexpress) C++11
100 / 100
 3 ms 504 KB 
#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*pi.fi) pq.push({ min((pi.se.se-Sem*pi.fi)/Loc+1, pi.se.fi-pi.fi) , make_pair(pi.se.fi-pi.fi, pi.se.se-Sem*pi.fi) });
	}
	printf("%lld\n", ans-1);
	return 0;
}

Compilation message

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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 380 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 424 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct

Subtask #3
52.0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 424 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 504 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 3 ms 504 KB Output is correct
29 Correct 2 ms 376 KB Output is correct
30 Correct 2 ms 376 KB Output is correct