Submission #361660

#	Time	Username	Problem	Language	Result	Execution time	Memory
361660		Dymo	도장 모으기 (JOI14_stamps)	C++14	100 / 100	153 ms	35912 KiB

stamps

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

#define ll int
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
const ll maxn =3e3+10;
const ll mod=1e9+7;
const ll base=1e9;
ll dp[maxn][maxn];

ll stayleft[maxn];
ll stayright[maxn];
ll toleft[maxn];
ll toright[maxn];
ll n,  t;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("A.inp","r"))
    {
        freopen("A.inp","r",stdin);
        freopen("A.out","w",stdout);
    }
    cin>> n>> t;
    for (int i=0;i<n;i++)
    {
      ll u, v, d, e;
       cin>> u>> v>> d>> e;
       stayleft[i]=d+e;
       stayright[i]=u+v;
       toleft[i]=u+e;
       toright[i]=v+d;
    }
    for (int i=0;i<=n;i++)
    {
        for (int j=0;j<=n;j++)
        {
           dp[i][j]=base;
        }
    }
    dp[0][0]=0;
    for (ll i=0;i<n;i++)
    {
        for (ll j=0;j<=n;j++)
        {
            if (j) dp[i][j]=min(dp[i][j],dp[i][j-1]-2*t*i+toright[i]);
        }
         for (ll j=n;j>=0;j--)
        {
            if (j<n) dp[i][j]=min(dp[i][j],dp[i][j+1]+2*t*i+toleft[i]);
        }
        for (ll j=0;j<=n;j++)
        {
            dp[i+1][j]=min(dp[i+1][j],dp[i][j]+stayright[i]);
            dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]-2*t*i+toright[i]);
            if (j) dp[i+1][j-1]=min(dp[i+1][j-1],dp[i][j]+2*t*i+toleft[i]);
            if (j) dp[i+1][j]=min(dp[i+1][j],dp[i][j]+stayleft[i]);
        }
    }
    ll ans=dp[n][0]+(n+1)*t;
    cout <<ans;




}

Compilation message (stderr)

stamps.cpp: In function 'int main()':
stamps.cpp:27:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   27 |         freopen("A.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~
stamps.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   28 |         freopen("A.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~

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