제출 #83477

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
83477		ekrem	Semiexpress (JOI17_semiexpress)	C++98	100 / 100	3 ms	1024 KiB

semiexpress

#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define N 1000005
using namespace std;
typedef long long ll;
typedef pair < ll , ll > ii;

ll n, m, k, A, B, C, ans = 0, a[N];
ll t;
priority_queue < pair < ii , ii > > q;

void ekle(ll bas, ll son, ll kal){
	if(bas > son or kal < 0)
		return;
	ll bul = 0;
	ll git = kal / A;
	if(bas + git <= son)
		bul = git + 1;
	else
		bul = son - bas + 1;
	// cout << bas << " " << son << " -> " << bul << " , " << kal << endl;
	q.push(mp(mp(bul, kal), mp(bas, son)));
}

void sil(){
	pair < ii , ii > x = q.top();
	ans += x.st.st;
	q.pop();
	ll bas = x.nd.st;
	ll son = x.nd.nd;
	ll kal = x.st.nd;

	ll git = kal / A;
	// cout << x.st.st << " " << bas << " " << son << " " << kal << " " << git << endl;
	ekle(bas + git + 1, son, kal - (git + 1)*C);
}

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%lld %lld %lld",&n ,&m ,&k); k -= m;
	scanf("%lld %lld %lld",&A ,&B ,&C);
	scanf("%lld",&t);
	for(ll i = 1; i <= m; i++)
		scanf("%lld",a + i);
	a[m + 1] = n + 1;
	for(ll i = 1; i <= m; i++){
		ll kal = t - (a[i] - 1)*B;
		if(kal < 0)
			break;
		ll git = kal / A;
		// cout << a[i] << " " << kal << " " << git << " " << a[i + 1] << endl;
		if(a[i] + git < a[i + 1]){
			ans += git + 1;
			// cout << "AMK = " << ans << endl;
			ekle(a[i] + git + 1, a[i + 1] - 1, kal - (git + 1)*C );
		}
		else
			ans += a[i + 1] - a[i];
	}
	// cout << "ans = " << ans << endl;
	// cout << endl << endl;
	while(!q.empty() and k--){
		sil();
	}
	printf("%lld\n", ans - 1);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld",&n ,&m ,&k); k -= m;
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld",&A ,&B ,&C);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&t);
  ~~~~~^~~~~~~~~~~
semiexpress.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",a + i);
   ~~~~~^~~~~~~~~~~~~~

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