比赛 |
10101115 |
评测结果 |
AAAAAAAAAA |
题目名称 |
矩形分割 |
最终得分 |
100 |
用户昵称 |
Citron酱 |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2010-11-15 08:45:09 |
显示代码纯文本
#include <fstream>
#include <cstdlib>
#define I_F "cut.in"
#define O_F "cut.out"
#define MAX 2000
using namespace std;
int s[MAX*2];
bool f[MAX*2];
long ans;
short n,m;
void Input();
void swap(short a, short b);
void Qsort(short l, short r);
void Imitate();
void Output();
int main()
{
Input();
Qsort(0,m+n-3);
Imitate();
Output();
return 0;
}
void Input()
{
ifstream fin(I_F);
fin>>n>>m;
short i;
for (i=0; i<n-1; i++)
{
fin>>s[i];
f[i]=true;
}
for (; i<m+n-2; i++)
{
fin>>s[i];
f[i]=false;
}
fin.close();
}
void swap(short a, short b)
{
int ts=s[a];
bool tf=f[a];
s[a]=s[b];
f[a]=f[b];
s[b]=ts;
f[b]=tf;
}
void Qsort(short l, short r)
{
int x=s[l+rand()%(r-l+1)];
int i=l, j=r;
do
{
while (s[i]>x)
i++;
while (s[j]<x)
j--;
if (i<=j)
swap(i++,j--);
} while (i<j);
if (i<r)
Qsort(i,r);
if (l<j)
Qsort(l,j);
}
void Imitate()
{
int s1=1, s2=1;
int i;
for (i=0; i<m+n-2; i++)
if (f[i])
{
ans+=s[i]*s1;
s2++;
}
else
{
ans+=s[i]*s2;
s1++;
}
}
void Output()
{
ofstream fout(O_F);
fout<<ans<<'\n';
fout.close();
}