oj.uz

Submission #69411

# Submission time Handle Problem Language Result Execution time Memory
69411 2018-08-20T19:11:33 Z MrTEK Semiexpress (JOI17_semiexpress) C++14
100 / 100
 3 ms 1284 KB 
#include <bits/stdc++.h>

using namespace std;
#define mp make_pair
#define pb push_back
#define len(a) (int)a.size()
#define fi first
#define sc second
#define d1(w) cerr<<#w<<":"<<w<<endl;
#define d2(w,c) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<endl;
#define d3(w,c,z) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<" "<<#z<<":"<<z<<endl;
#define left isc+isc
#define right isc+isc+1
#define mid (l+r)/2
#define FAfi_IO ios_base::sync_with_fidio(false);
#define escl '\n'

typedef long long int ll;

const int maxn = 620;
const long long LINF = 1e18;
const int LOG = 31;
const int INF = 1e9;
const int N = 3e3 + 5;
const int M = 1e4 + 5;
const int SQ = 350;
const int MOD = 998244353;

typedef long long int lli;
typedef pair<int,int> pii;

priority_queue <pair <long long,int> > Q;

int n,m,k,mx,s[N];
long long t,a,b,c,ans,rem[N];

long long calc(int ind) {
	long long tut = (t - (s[ind] - 1) * b - (s[ind + 1] - s[ind] - 1 - rem[ind]) * c);
	if (tut < c) return 0;
	return min(rem[ind],(tut - c) / a + 1);	
}


int main() {

	scanf("%d %d %d %lld %lld %lld %lld",&n,&m,&k,&a,&b,&c,&t);
	for (int i = 1 ; i <= m ; i++)
		scanf("%d",&s[i]);
	for (int i = 1 ; i < m ; i++) {
		if ((s[i] - s[1]) * b > t) break;
		mx = i;
	}
	for (int i = 1 ; i <= mx ; i++) {
		rem[i] = max(0ll,(s[i + 1] - s[i] - 1) - (t - (s[i] - 1) * b) / a);
		Q.push(mp(calc(i),i));
	}
	k -= m;
	while(k--) {
		long long temp = Q.top().fi;
		int ind = Q.top().sc;
		Q.pop();
		rem[ind] -= temp;
		Q.push(mp(calc(ind),ind));
	}
	for (int i = 1 ; i <= mx ; i++)
		ans += s[i + 1] - s[i] - rem[i];
	if ((s[m] - 1) * b <= t) ans++;
	printf("%lld\n",ans - 1);
}

Compilation message

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

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 580 KB Output is correct
3 Correct 2 ms 608 KB Output is correct
4 Correct 2 ms 608 KB Output is correct
5 Correct 2 ms 660 KB Output is correct
6 Correct 3 ms 816 KB Output is correct
7 Correct 2 ms 832 KB Output is correct
8 Correct 2 ms 836 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 580 KB Output is correct
3 Correct 2 ms 608 KB Output is correct
4 Correct 2 ms 608 KB Output is correct
5 Correct 2 ms 660 KB Output is correct
6 Correct 3 ms 816 KB Output is correct
7 Correct 2 ms 832 KB Output is correct
8 Correct 2 ms 836 KB Output is correct
9 Correct 2 ms 848 KB Output is correct
10 Correct 2 ms 848 KB Output is correct
11 Correct 2 ms 972 KB Output is correct
12 Correct 2 ms 972 KB Output is correct
13 Correct 2 ms 996 KB Output is correct
14 Correct 2 ms 1016 KB Output is correct
15 Correct 2 ms 1024 KB Output is correct
16 Correct 2 ms 1024 KB Output is correct
17 Correct 2 ms 1024 KB Output is correct
18 Correct 2 ms 1024 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 580 KB Output is correct
3 Correct 2 ms 608 KB Output is correct
4 Correct 2 ms 608 KB Output is correct
5 Correct 2 ms 660 KB Output is correct
6 Correct 3 ms 816 KB Output is correct
7 Correct 2 ms 832 KB Output is correct
8 Correct 2 ms 836 KB Output is correct
9 Correct 2 ms 848 KB Output is correct
10 Correct 2 ms 848 KB Output is correct
11 Correct 2 ms 972 KB Output is correct
12 Correct 2 ms 972 KB Output is correct
13 Correct 2 ms 996 KB Output is correct
14 Correct 2 ms 1016 KB Output is correct
15 Correct 2 ms 1024 KB Output is correct
16 Correct 2 ms 1024 KB Output is correct
17 Correct 2 ms 1024 KB Output is correct
18 Correct 2 ms 1024 KB Output is correct
19 Correct 2 ms 1048 KB Output is correct
20 Correct 2 ms 1084 KB Output is correct
21 Correct 2 ms 1096 KB Output is correct
22 Correct 3 ms 1128 KB Output is correct
23 Correct 3 ms 1272 KB Output is correct
24 Correct 2 ms 1272 KB Output is correct
25 Correct 2 ms 1272 KB Output is correct
26 Correct 2 ms 1272 KB Output is correct
27 Correct 3 ms 1272 KB Output is correct
28 Correct 3 ms 1272 KB Output is correct
29 Correct 2 ms 1276 KB Output is correct
30 Correct 2 ms 1284 KB Output is correct