比赛 |
SBOI2022暑假快乐赛① |
评测结果 |
AAAWAWWWWW |
题目名称 |
士兵放假了 |
最终得分 |
40 |
用户昵称 |
ZRQ |
运行时间 |
8.893 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2022-06-25 11:08:34 |
显示代码纯文本
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<cmath>
using namespace std;
const int N=200005,INF=0xcf3f3f3f;
struct node
{
double at;
int op;
}p[N];
int n,m,k,cnt,ans=INF;
char ch;
void read(int &x){x=0;ch=getchar();while(ch<47||ch>58)ch=getchar();while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch^48),ch=getchar();}
int random(int n)
{
return (unsigned long long)rand()*rand()%n+1;
}
int calc()
{
double num=k;
for(int i=1;i<=n;++i)
{
if(p[i].op==1) num=(num+p[i].at);
else if(p[i].op==2) num=(num-p[i].at);
else if(p[i].op==3) num=(num*p[i].at);
else num=(num/p[i].at);
}
return (int)num;
}
void SA()
{
random_shuffle(p+1,p+1+n);
for(double t=1e4;t>=1e-4;t*=0.97)
{
int x=calc();
cnt=max(cnt,x);
int p1=random(n),p2=random(n);
while(p1==p2) p1=random(n);
swap(p[p1],p[p2]);
int y=calc();
cnt=max(cnt,y);
if(exp(-(y-x)/t)>(double)clock()/RAND_MAX) swap(p[p1],p[p2]);
}
ans=max(ans,cnt);
return ;
}
int main()
{
freopen("holiday_and_angryF.in","r",stdin);
freopen("holiday_and_angryF.out","w",stdout);
srand(19260817);
int at;
read(n),read(m),read(at);
k=(double)at;
for(int i=1;i<=n;++i)
{
read(at);
p[i].at=(double)at;
char op=getchar();
if(op=='+') p[i].op=1;
else if(op=='-') p[i].op=2;
else if(op=='*') p[i].op=3;
else p[i].op=4;
}
while((double)clock()/CLOCKS_PER_SEC<0.95) SA();
if(ans>m) printf("YES\n");
else printf("NO\n");
printf("%d\n",ans);
return 0;
}