Submission #715940

#	Time	Username	Problem	Language	Result	Execution time	Memory
715940		vinnipuh01	Semiexpress (JOI17_semiexpress)	C++17	18 / 100	1 ms	212 KiB

semiexpress

#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <map>
#include <queue>
#define int long long
#define sqrt sqrtl

using namespace std;

const long long oo = 1000000000000000000;

long long sum, ans = 0, mx = 0, mn = 1000000000, num, pos;


/*
    ViHHiPuh

   (( `'-""``""-'` ))
     )-__-_.._-__-(
   / --- (o _ o) --- \
   \ .-* ( .0. ) *-. /
   _'-. ,_ '=' _, .-'_
  / `;#'#'# - #'#'#;` \
 \_)) -----'#'----- ((_/
      # --------- #
  '# ------- ------ #'
  /..-'# ------- #'-.\
  _\...-\'# -- #'/-.../_
  ((____)- '#' -(____))


    cout << fixed << setprecision(6) << x;

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    freopen ( "sum.in", "r", stdin )
*/

int n, m, k, x, b, c, t, a[ 3002 ];
set <pair<int, int> > st;
vector <int> v;

main () {
	cin >> n >> m >> k;
	cin >> x >> b >> c;
	cin >> t;
	v.push_back( 1 );
	for ( int i = 1; i <= m; i ++ ) {
		cin >> a[ i ];
		if ( b * ( a[ i ] - 1 ) <= t )
			v.push_back( a[ i ] );
	}
	pos = 1;
	sum = 0;
	num = 0;
	v.push_back( n + 1 );
	while ( pos <= n ) {
		if ( sum > t )
			break;
		int next = pos + ( t - sum ) / x;
		if ( v[ num ] - 1 > next ) {
			st.insert( { v[ num ] - ( next + 1 ), next + 1 } );
			pos = v[ num ];
			sum = b * ( v[ num ] - 1 );
			num ++;
		}
		else {
			pos = v[ num ];
			sum = b * ( v[ num ] - 1 );
			num ++;
		}
	}
//	for ( auto i : st )
//		cout << i.first << " " << i.second << "\n";
	k -= m;
	while ( st.size() && k ) {
		pos = st.rbegin()->second;
		int tt = st.rbegin()->first;
		int l, r, mid;
		st.erase( --st.end() );
		k --;
		l = 0;
		r = v.size() - 1;
		while ( r > l ) {
			mid = ( l + r ) / 2;
			if ( v[ mid ] > pos )
				r = mid;
			else
				l = mid + 1;
		}
		l --;
		sum = ( pos - v[ l ] ) * c;
		sum += ( v[ l ] - 1 ) * b;
		if ( sum > t ) {
			ans += tt;
			k ++;
			continue;
		}
		int next = pos + ( t - sum ) / x;
		l = 0;
		r = v.size() - 1;
		while ( r > l ) {
			mid = ( l + r ) / 2;
			if ( v[ mid ] > pos )
				r = mid;
			else
				l = mid + 1;
		}
		num = l;
		if ( next >= v[ num ] - 1 )
			continue;
		st.insert( { v[ num ] - ( next + 1 ), next + 1 } );
	}
	ans += 1;
	for ( auto i : st ) {
		ans += i.first;
	}
	cout << n - ans;
}

Compilation message (stderr)

semiexpress.cpp:51:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   51 | main () {
      | ^~~~

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