QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#694215#5417. Chat ProgramYuanyin26TL 19ms5220kbC++201.4kb2024-10-31 17:28:562024-10-31 17:28:58

Judging History

你现在查看的是最新测评结果

  • [2024-10-31 17:28:58]
  • 评测
  • 测评结果:TL
  • 用时:19ms
  • 内存:5220kb
  • [2024-10-31 17:28:56]
  • 提交

answer

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<string.h>
#include <string>
#include<math.h>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<map>
#include<queue>
#include<stack>
#include<functional>
#include<deque>
using namespace std;

#define MAXN 301000;
#define ll long long
#define lll unsigned long long
#define PA pair<ll,ll>
#define INF (ll)0x3f3f3f3f*(ll)1000000
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N = 2e5 + 7;
const ll mod = 1e9 + 7;
int n, k, m, c,d;
int a[N];
bool check(int x)
{
	vector<int>cf(n + 2, 0);
	for (int i = 1; i <= n; i++)
	{
		if (a[i] >= x)cf[1]++;
		else if (a[i] + c + min(i-1,(m - 1)) * d < x);
		else 
		{
			int in;
			if (d == 0)
			{
				in = 0;
			}
			else 
				in = ((x - a[i] - c)+(d-1)) / d;
			int l = i - m + 1 >= 0 ? i - m + 1 : 1, r = i - in  >= 0 ? i - in  : 1;
			cf[l]++, cf[r + 1]--;
		}
	}
	for (int i = 1; i <= n; i++)
	{
		cf[i] = cf[i - 1] + cf[i];
		if (cf[i] >= k)return true;
	}
	return false;
}
void solve()
{
	cin >> n >> k >> m >> c >> d;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];

	}
		
	int l = -1, r = 1e19;
	while (l + 1 != r)
	{
		int mid = (l + r) >> 1;
		if (check(mid))l = mid;
		else r = mid;
	}
	cout << l << endl;
}
int main() {
	IOS;
	int t = 1;// cin >> t;
	while (t--) {
		solve();
	}
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3588kb

input:

6 4 3 1 2
1 1 4 5 1 4

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

7 3 2 4 0
1 9 1 9 8 1 0

output:

9

result:

ok 1 number(s): "9"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3700kb

input:

8 3 5 0 0
2 0 2 2 1 2 1 8

output:

2

result:

ok 1 number(s): "2"

Test #4:

score: 0
Accepted
time: 19ms
memory: 5220kb

input:

200000 200000 100000 0 1000000000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: -100
Time Limit Exceeded

input:

200000 1 100000 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 100000000...

output:


result: