Submission #1193878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193878		vnedu	도장 모으기 (JOI14_stamps)	C++17	10 / 100	434 ms	34224 KiB

stamps

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }

#define fi first
#define se second

#define pb push_back
#define ii pair<int, int>

#define all(x) x.begin(), x.end()

#define TASK "nonsense"

/// end of template ///

const int N = 3000 + 10;
int n,t;
struct Plat
{
    int u,v,d,e;
    Plat() {}
    void input()
    {
        cin>>u>>v>>d>>e;
    }
} plat[N];
namespace sub1
{
    bool check()
    {
        return (n<=16);
    }
    const int N = 16;
    const ll inf = 1e18;
    vector<ii> adj[3*N+2];
    ll dp[3*N+2][1<<N];
    struct node
    {
        int u,mask;
        ll dis;
        node() {}
        node(int u, int mask, ll dis) : u(u),mask(mask),dis(dis) {}

        bool operator < (const node &S) const
        {
            return dis>S.dis;
        }
    };
    priority_queue<node> pq;
    void solve()
    {
        for(int i=0;i<n;++i) adj[i].pb({i+1,t});
        adj[n].pb({3*n+1,t});
        for(int i=3*n;i>2*n+1;--i) adj[i].pb({i-1,t});
        for(int i=1;i<=n;++i)
        {
            adj[i].pb({i+n,plat[i].u});
            adj[i+n].pb({i,plat[i].v});
            adj[i+2*n].pb({i+n,plat[i].d});
            adj[i+n].pb({i+2*n,plat[i].e});
        }
        for(int i=0;i<3*N+2;++i) for(int j=0;j<(1<<N);++j) dp[i][j]=inf;
        dp[0][0]=0;
        pq.push(node(0,0,0));
        while(!pq.empty())
        {
            node cur=pq.top(); pq.pop();
            if(cur.dis!=dp[cur.u][cur.mask]) continue;
//            if(cur.u==3*n+1) cout<<cur.u<<' '<<cur.mask<<' '<<cur.dis<<'\n';
            for(ii p : adj[cur.u])
            {
                int v=p.fi,w=p.se;
//                cout<<v<<' '<<w<<'\n';
                int nmask=cur.mask;
                if(v>=n+1 && v<=n+n) nmask|=(1<<(v-(n+1)));
//                cout<<dp[cur.u][cur.mask]<<'\n';
                if(dp[cur.u][cur.mask]+w<dp[v][nmask])
                {
//                    cout<<"DSA";
                    dp[v][nmask]=dp[cur.u][cur.mask]+w;
                    pq.push(node(v,nmask,dp[v][nmask]));
                }
            }
        }
        cout<<dp[3*n+1][(1<<n)-1];
    }
}
namespace sub2
{
    bool check()
    {
        return (n<=100);
    }
    const int N = 100 + 5;
    const ll inf = 1e18;
    ll dp[N][N];
    void solve()
    {
        for(int i=0;i<N;++i) for(int j=0;j<N;++j) dp[i][j]=inf;
        dp[0][0]=0;
        for(int i=0;i<n;++i) for(int k=0;k<n;++k) if(dp[i][k]!=inf)
        {
//            cout<<i<<' '<<k<<'\n';
            for(int close=0;close<=1;++close)
            {
                int open=0;
                if(k-close+open>=n || k-close+open<0) continue;
                ll sum=dp[i][k]+(plat[i+1].u+plat[i+1].e)*1LL*close+(plat[i+1].d+plat[i+1].v)*1LL*open+2LL*(i+1)*t*(close-open);
                if(max(open,close)==0)
                {
                    if(k==0) sum+=plat[i+1].u+plat[i+1].v;
                    else sum+=min(plat[i+1].u+plat[i+1].v,plat[i+1].d+plat[i+1].e);
                }
                minimize(dp[i+1][k-close+open],sum);
            }
            for(int open=0;open<=1;++open)
            {
                int close=0;
                if(k-close+open>=n || k-close+open<0) continue;
                ll sum=dp[i][k]+(plat[i+1].u+plat[i+1].e)*1LL*close+(plat[i+1].d+plat[i+1].v)*1LL*open+2LL*(i+1)*t*(close-open);
                if(max(open,close)==0)
                {
                    if(k==0) sum+=plat[i+1].u+plat[i+1].v;
                    else sum+=min(plat[i+1].u+plat[i+1].v,plat[i+1].d+plat[i+1].e);
                }
                minimize(dp[i+1][k-close+open],sum);
            }
        }
        cout<<dp[n][0]+(n+1)*1LL*t;
    }
}
void solve()
{
    cin>>n>>t;
    for(int i=1;i<=n;++i) plat[i].input();
    if(sub1::check()) return void(sub1::solve());
    if(sub2::check()) return void(sub2::solve());
}
int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);

    int testcase=1;
//    cin>>testcase;

    while (testcase--)
        solve();

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 75
• Subtask 3: 0 / 15