oj.uz

Submission #361660

# Submission time Handle Problem Language Result Execution time Memory
361660 2021-01-31T03:50:31 Z Dymo 도장 모으기 (JOI14_stamps) C++14
100 / 100
 153 ms 35912 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 32 ms 364 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 396 KB Output is correct
3 Correct 2 ms 748 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 748 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 1 ms 748 KB Output is correct
10 Correct 1 ms 748 KB Output is correct
11 Correct 1 ms 748 KB Output is correct
12 Correct 1 ms 748 KB Output is correct
13 Correct 1 ms 896 KB Output is correct
14 Correct 2 ms 748 KB Output is correct
15 Correct 1 ms 748 KB Output is correct
16 Correct 2 ms 748 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 35820 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 151 ms 35912 KB Output is correct
4 Correct 118 ms 31724 KB Output is correct
5 Correct 105 ms 27872 KB Output is correct
6 Correct 44 ms 15468 KB Output is correct
7 Correct 25 ms 10220 KB Output is correct
8 Correct 151 ms 35820 KB Output is correct
9 Correct 150 ms 35872 KB Output is correct
10 Correct 149 ms 35820 KB Output is correct
11 Correct 150 ms 35820 KB Output is correct
12 Correct 150 ms 35820 KB Output is correct
13 Correct 150 ms 35868 KB Output is correct
14 Correct 150 ms 35820 KB Output is correct
15 Correct 153 ms 35820 KB Output is correct
16 Correct 150 ms 35820 KB Output is correct
17 Correct 149 ms 35820 KB Output is correct