QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#351516#2375. Life Transferspiros_galWA 0ms3684kbC++142.0kb2024-03-12 00:00:392024-03-12 00:00:40

Judging History

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

  • [2024-03-12 00:00:40]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3684kb
  • [2024-03-12 00:00:39]
  • 提交

answer

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int n, k;
long long lc, pc, lm, pm;
long long t, d;
vector <long long> a;
vector <long long> disp;
vector <long long> dispc;
vector <long long> dispm;
vector <long long> needc;
vector <long long> needm;
bool can;

void printv(vector <long long> &v) {
	for(auto u : v) {
		cout << u << " ";
	}

	cout << endl;
}

int main() {
	cin >> n >> k;
	cin >> lc >> pc >> lm >> pm;
	cin >> t >> d;
	a.resize(n);
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}

	sort(a.begin(), a.end());
	disp.resize(n + 1);
	dispc.resize(n + 1);
	dispm.resize(n + 1);
	needc.resize(n + 1);
	needm.resize(n + 1);

	can = false;

	for(int i = 0; i < n; i++) {
		disp[i + 1] = disp[i];
		disp[i + 1] += min(a[i] - 1, d);

		dispc[i + 1] = dispc[i];
		needc[i + 1] = needc[i];
		if(a[i] < lc) needc[i + 1] += lc - a[i];
		else dispc[i + 1] += min(a[i] - lc, d);

		dispm[i + 1] = dispm[i];
		needm[i + 1] = needm[i];
		if(a[i] < lm) needm[i + 1] += lm - a[i];
		else dispm[i + 1] += min(a[i] - lm, d);
	}

	// printv(a);
	// printv(disp);
	// printv(dispc);
	// printv(dispm);
	// printv(needc);
	// printv(needm);

	long long currmin = LLONG_MAX;
	for(int i = 0; i * k <= n; i++) {
		long long cost = ((long long)i) * pc + ((long long) n - i * k) * pm;
		long long disp_total = disp[i * k - i] - disp[0];
		long long need_total = 0;
		int cntm = n - i * k;
		disp_total += dispm[n - i] - dispm[i * k - i];
		disp_total += dispc[n] - dispc[n - i];
		need_total += needm[n - i] - needm[i * k - i];
		need_total += needc[n] - needc[n - i];
		//cout << "i=" << i << " disp_total=" << disp_total << " need_total=" << need_total << endl;
		if(i && (a[n - i] < lc - d)) continue;
		if(cntm && (a[i * k - i] < lm - d)) continue;

		if(need_total > disp_total) continue;
		can = true;
		cost += need_total * t;
		currmin = min(currmin, cost);
	}

	cout << ((can) ? currmin : -1) << endl; 
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 2
18 1000 16 1
5 3
16 15

output:

1010

result:

ok single line: '1010'

Test #2:

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

input:

2 2
23 10 15 5
2 2
9 20

output:

-1

result:

ok single line: '-1'

Test #3:

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

input:

51 23
97 60 21 6
69 30
54 61 34 14 73 86 72 84 54 96 49 48 4 71 7 4 75 17 64 52 3 40 51 25 70 21 79 61 54 50 23 45 24 87 50 82 58 28 71 43 15 22 28 34 98 30 36 36 12 14 90

output:

219

result:

ok single line: '219'

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3684kb

input:

62 76
65 65 8 10
7 72
94 1 11 41 83 91 4 70 19 28 47 64 30 32 32 92 72 9 67 39 29 26 83 65 79 45 4 90 18 79 47 70 47 1 45 29 61 35 76 36 100 52 21 1 25 73 44 17 50 6 73 22 58 69 97 72 5 47 45 2 16 54

output:

900

result:

wrong answer 1st lines differ - expected: '65', found: '900'