QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#687264#6471. Binary TransformationsPetroTarnavskyi#WA 0ms3844kbC++231.5kb2024-10-29 17:54:222024-10-29 17:54:22

Judging History

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

  • [2024-10-29 17:54:22]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3844kb
  • [2024-10-29 17:54:22]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef double db;

struct node
{
	int c;
	char state, need;
	
	bool operator<(const node& n) const
	{
		return c < n.c;
	}
};

LL solve(int n, vector<node> vals)
{
	LL ans = 0;
	LL sum = 0;
	FOR(i, 0, n)
		if(vals[i].state == '1')
			sum += vals[i].c;
	
	RFOR(i, n, 0)
	{
		if(vals[i].state == '1' && vals[i].need == '0')
		{
			sum -= vals[i].c;
			ans += sum;
		}
	}
	FOR(i, 0, n)
	{
		if(vals[i].state == '0' && vals[i].need == '1')
		{
			sum += vals[i].c;
			ans += sum;
		}
	}
	return ans;
}


int main()
{
	ios::sync_with_stdio(0); 
	cin.tie(0);

	int n;
	cin >> n;
	
	vector<node> vals(n);
	FOR(i, 0, n)
		cin >> vals[i].c;
	FOR(i, 0, n)
		cin >> vals[i].state;
	FOR(i, 0, n)
		cin >> vals[i].need;
	
	sort(ALL(vals));
	
	LL ans = solve(n, vals);
	
	LL sum = 0;
	FOR(i, 0, n)
		sum += vals[i].c;
		
	LL cur = 0;
	RFOR(i, n, 0)
	{
		if(vals[i].state == '0')
			continue;
		vals[i].state = '0';
		
		sum -= vals[i].c;
		cur += sum;
		
		ans = min(ans, cur + solve(n, vals));
	}
	cout << ans << "\n";
	
	
	
	

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
5 2 6 1 5
01110
10011

output:

21

result:

ok single line: '21'

Test #2:

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

input:

10
54 57 56 56 34 26 62 57 94 93
1101100111
0111110011

output:

1498

result:

ok single line: '1498'

Test #3:

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

input:

100
13497 84812 46650 96837 47518 81363 69563 49672 62222 59492 2399 70142 66019 23108 34561 48256 89591 70076 35039 20871 56909 44505 91578 96372 47174 73772 45594 75368 50125 79114 39144 60524 75020 85709 33811 68779 99668 89361 25932 45107 41881 70392 77449 37880 20372 49639 24933 76529 43903 136...

output:

89174223

result:

wrong answer 1st lines differ - expected: '83548857', found: '89174223'