Submission #1693808


Source Code Expand

#include <cstdio>
#include <cstring>
#include <set>
#define MAXN 100010
#define LL long long
using namespace std;

int n1,n2,n3,n;
int a[MAXN][4],b[MAXN];
multiset< pair<int,int> > S[4][4];
LL ans=0;

int query(int x,int y){
	if(S[x][y].empty() || S[y][x].empty()) return 0;
	return S[x][y].rbegin()->first+S[y][x].rbegin()->first;
}

int query(int x,int y,int z){
	if(S[x][y].empty() || S[y][z].empty() || S[z][x].empty()) return 0;
	return S[x][y].rbegin()->first+S[y][z].rbegin()->first+S[z][x].rbegin()->first;
}

void gao(int v0,int v1){
	int x=S[v0][v1].rbegin()->second;
	for(int j=1;j<=3;j++)
		if(j^b[x])
			S[b[x]][j].erase(S[b[x]][j].find(make_pair(a[x][j]-a[x][b[x]],x)));
	b[x]=v1;
	for(int j=1;j<=3;j++)
		if(j^b[x])
			S[b[x]][j].insert(make_pair(a[x][j]-a[x][b[x]],x));
}

bool gao(){
	int res=0;
	int s12=query(1,2); res=max(res,s12);
	int s13=query(1,3); res=max(res,s13);
	int s23=query(2,3); res=max(res,s23);
	int s123=query(1,2,3); res=max(res,s123);
	int s132=query(1,3,2); res=max(res,s132);
	if(!res) return 0;
	if(s12==res) gao(1,2),gao(2,1);
	else if(s13==res) gao(1,3),gao(3,1);
	else if(s23==res) gao(2,3),gao(3,2);
	else if(s123==res) gao(1,2),gao(2,3),gao(3,1);
	else if(s132==res) gao(1,3),gao(3,2),gao(2,1);
	ans+=res;
	return 1;
}

int main(){
#ifdef DEBUG
	freopen("C.in","r",stdin);
#endif
	scanf("%d%d%d",&n1,&n2,&n3);
	n=n1+n2+n3;
	for(int i=1;i<=n;i++)
		scanf("%d%d%d",&a[i][1],&a[i][2],&a[i][3]);
	for(int i=1;i<=n1;i++){
		int x=i;
		b[x]=1;
		ans+=a[x][b[x]];
		for(int j=1;j<=3;j++)
			if(j^b[x])
				S[b[x]][j].insert(make_pair(a[x][j]-a[x][b[x]],x));
	}
	for(int i=1;i<=n2;i++){
		int x=i+n1;
		b[x]=2;
		ans+=a[x][b[x]];
		for(int j=1;j<=3;j++)
			if(j^b[x])
				S[b[x]][j].insert(make_pair(a[x][j]-a[x][b[x]],x));
	}
	for(int i=1;i<=n3;i++){
		int x=i+n1+n2;
		b[x]=3;
		ans+=a[x][b[x]];
		for(int j=1;j<=3;j++)
			if(j^b[x])
				S[b[x]][j].insert(make_pair(a[x][j]-a[x][b[x]],x));
	}
	while(gao());
	printf("%lld\n",ans);
}

Submission Info

Submission Time
Task C - Coins
User ez_zjt
Language C++14 (GCC 5.4.1)
Score 800
Code Size 2058 Byte
Status AC
Exec Time 194 ms
Memory 13568 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:55:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n1,&n2,&n3);
                             ^
./Main.cpp:58:45: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&a[i][1],&a[i][2],&a[i][3]);
                                             ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 800 / 800
Status
AC × 3
AC × 35
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
subtask_1_01.txt AC 1 ms 256 KB
subtask_1_02.txt AC 20 ms 2176 KB
subtask_1_03.txt AC 20 ms 3712 KB
subtask_1_04.txt AC 76 ms 6144 KB
subtask_1_05.txt AC 89 ms 7040 KB
subtask_1_06.txt AC 128 ms 9088 KB
subtask_1_07.txt AC 26 ms 2944 KB
subtask_1_08.txt AC 120 ms 9728 KB
subtask_1_09.txt AC 25 ms 2560 KB
subtask_1_10.txt AC 111 ms 8704 KB
subtask_1_11.txt AC 164 ms 11520 KB
subtask_1_12.txt AC 71 ms 11520 KB
subtask_1_13.txt AC 132 ms 11520 KB
subtask_1_14.txt AC 163 ms 13568 KB
subtask_1_15.txt AC 194 ms 11520 KB
subtask_1_16.txt AC 135 ms 11520 KB
subtask_1_17.txt AC 137 ms 11520 KB
subtask_1_18.txt AC 163 ms 11520 KB
subtask_1_19.txt AC 164 ms 11520 KB
subtask_1_20.txt AC 186 ms 11520 KB
subtask_1_21.txt AC 74 ms 11520 KB
subtask_1_22.txt AC 172 ms 11520 KB
subtask_1_23.txt AC 158 ms 11520 KB
subtask_1_24.txt AC 182 ms 11520 KB
subtask_1_25.txt AC 102 ms 11520 KB
subtask_1_26.txt AC 150 ms 11648 KB
subtask_1_27.txt AC 164 ms 11648 KB
subtask_1_28.txt AC 159 ms 11520 KB
subtask_1_29.txt AC 1 ms 256 KB