Submission #715991

#	Time	Username	Problem	Language	Result	Execution time	Memory
715991		vinnipuh01	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	10 ms	340 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<pair<int, int> , int> > st;
vector <int> v;

main () {
	cin >> n >> m >> k;
	cin >> x >> b >> c;
	cin >> t;
	a[ 0 ] = 1;
	for ( int i = 1; i <= m; i ++ ) {
		cin >> a[ i ];
	}
	a[ m + 1 ] = n;
	pos = 1;
	num = 0;
	for ( int i = 1; i <= m; i ++ ) {
		if ( num > t ) {
			st.insert( { make_pair( a[ i - 1 ], n ), ( pos - 1 ) * b } );
			break;
		}
		pos = pos + ( t - num ) / x;
		if ( pos < a[ i ] - 1 )
			st.insert( { make_pair( pos + 1, a[ i ] - 1 ), ( a[ i - 1 ] - 1 ) * b + ( pos + 1 - a[ i - 1 ] ) * c } );
		num = ( a[ i ] - 1 ) * b;
		pos = a[ i ];
	}
	if ( num <= t ) {
		pos = pos + ( t - num ) / x;
		if ( pos < n ) {
			st.insert( { make_pair( pos + 1, n ), ( a[ m ] - 1 ) * b + ( pos + 1 - a[ m ] ) * c } );
		}
	}
	else {
		st.insert( { make_pair( pos, n ), ( pos - 1 ) * b } );
	}
	k -= m;
	int last, cost, next;
	while ( k -- ) {
		pair<pair<int, int>, int> p;
		p.first.first = -1;
		mx = 0;
		for ( auto i : st ) {
			pos = i.first.first;
			last = i.first.second;
			cost = i.second;
			if ( cost > t )
				continue;
			next = pos + ( t - cost ) / x;
			next = min( next, last );
			if ( next - pos + 1 > mx ) {
				mx = next - pos + 1;
				p = i;
			}
		}
		if ( p.first.first == -1 )
			continue;
		st.erase( p );
		pos = p.first.first;
		last = p.first.second;
		cost = p.second;
		next = pos + ( t - cost ) / x;
		next = min( next, last );
		if ( next != last )
			st.insert( { make_pair( next + 1, last ), cost + ( next + 1 - pos ) * c } );
	}
	ans = 1;
	for ( auto i : st ) 
		ans += i.first.second - i.first.first + 1;
	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: 30 / 30
• Subtask 3: 52 / 52