제출 #1159742

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1159742		brover29	Semiexpress (JOI17_semiexpress)	C++17	0 / 100	0 ms	320 KiB

semiexpress

#include <bits/stdc++.h>
//qwerty47924692
using namespace std;
using ll = long long;
const ll N=305;
const string br="617283";
#define sz(a)(ll)a.size()
#define f first
#define s second
ll n,m,k,a,b,c,t,d[N],used[N],was[N];
vector<ll>s,ss;
vector<pair<ll,ll>>g[N];
void djikstra(ll s){
    for(ll i=1;i<=n;i++){
        d[i]=1e18;
        used[i]=0;
    }
    d[s]=0;
    priority_queue<pair<ll,ll>>q;
    q.push({0,s});
    while(q.size()){
        ll v=q.top().s;
        q.pop();
       // cout<<v<<' '<<d[v]<<'\n';
        if(used[v])continue;
        used[v]=1;
        for(auto [to,w]:g[v]){
            if(d[to]>d[v]+w){
                d[to]=d[v]+w;
                if(to==3&&d[to]==8)cout<<v<<' '<<d[v]<<' '<<w<<'\n';
                q.push({-d[to],to});
            }
        }
    }
}ll calc(ll i,ll j){
    for(ll i=1;i<=n;i++)g[i].clear();
    ss=s;
    ss.push_back(i);
    ss.push_back(j);
    sort(ss.begin(),ss.end());
    for(ll i=1;i<s.size();i++){
        ll u=s[i-1];
        ll v=s[i];
       // g[v].push_back(make_pair(u,b));
        g[u].push_back({v,b});
    }for(ll i=2;i<=n;i++){
        ll v=i;
        ll u=i-1;
      //  g[v].push_back({u,a});
        g[u].push_back({v,a});
    }for(ll i=1;i<ss.size();i++){
        ll v=ss[i];
        ll u=ss[i-1];
      //  cout<<v<<' '<<u<<'\n';
     //   g[v].push_back({u,c});
        g[u].push_back({v,c});
    }
    djikstra(1);
    ll cnt=0;
    for(ll i=1;i<=n;i++){

        if(d[i]<=t){
            cnt++;
        }
    }
    cout<<cnt;
    return cnt;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>m>>k>>a>>b>>c>>t;
    ll ans=0;
    for(ll i=1;i<=m;i++){
        ll v;
        cin>>v;
        was[v]=1;
        s.push_back(v);
    }
    for(ll i=1;i<=n;i++){
        if(was[i])continue;
        for(ll j=i+1;j<=n;j++){
            if(was[j])continue;
            ans=max(ans,calc(i,j));
        //    cout<<i<<' '<<j<<' '<<calc(i,j)<<'\n';
            return 0;
        }
    }
    cout<<ans;
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 30
• Subtask 3: 0 / 52