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
2017-10-19 21:15:28+0900
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
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