Submission #1193952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193952		vnedu	도장 모으기 (JOI14_stamps)	C++17	100 / 100	421 ms	71396 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 subfull
{
    const ll inf = 1e18;
    ll dp[N][N],p[N],s[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=1;i<=n;++i)
        {
            for(int k=0;k<n;++k)
            {
                p[k]=(k==0?inf:p[k-1]);
                if(dp[i-1][k]!=inf) minimize(p[k],dp[i-1][k]-k*(plat[i].d+plat[i].v-2LL*i*t));
                if(k>0 && p[k-1]!=inf) minimize(dp[i][k],p[k-1]+k*(plat[i].d+plat[i].v-2LL*i*t));
            }
            s[n]=inf;
            for(int k=n-1;k>=0;--k)
            {
                s[k]=min(s[k+1],dp[i-1][k]+k*(plat[i].u+plat[i].e+2LL*i*t));
                if(s[k+1]!=inf) minimize(dp[i][k],s[k+1]-k*(plat[i].u+plat[i].e+2LL*i*t));
            }
            for(int k=0;k<n;++k) if(dp[i-1][k]!=inf)
            {
                ll sum=dp[i-1][k];
                if(k==0) sum+=plat[i].u+plat[i].v;
                else sum+=min(plat[i].u+plat[i].v,plat[i].d+plat[i].e);
                minimize(dp[i][k],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());
    return void(subfull::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: 75 / 75
• Subtask 3: 15 / 15