oj.uz

답안 #715991

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
715991 2023-03-28T17:48:59 Z vinnipuh01 Semiexpress (JOI17_semiexpress) C++17
100 / 100
 10 ms 340 KB 
#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

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

Subtask #1
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 304 KB Output is correct

Subtask #2
30.0 / 30.0

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

Subtask #3
52.0 / 52.0

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