比赛 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;
}