Submission #361658

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

stamps

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "test"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 3e3 + 5;
const int logn = log2(maxn) + 1;

int dp[maxn][maxn];
int n , t;
int ToRight[maxn] , ToLeft[maxn] , StayLeft[maxn] , StayRight[maxn];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    fill_n(&dp[0][0],maxn*maxn,1e9);
    cin >> n >> t;
    for(int i = 0 ; i < n ; ++i){
        int u , v , d , e;cin >> u >> v >> d >> e;
        ToRight[i] = d + v;
        ToLeft[i] = u + e;
        StayRight[i] = u + v;
        StayLeft[i] = d + e;
    }
    dp[0][0] = 0;
    auto Min = [&](int & x , int y){
        if(x > y)x = y;
    };
    for(int i = 0 ; i < n ; ++i){
        for(int j = 0 ; j <= n ; ++j){//move backward j time left.
            if(j > 0)Min(dp[i][j] , dp[i][j - 1] + ToRight[i] - 2 * t * i);//Create another path later return to i.
            if(j > 0)Min(dp[i + 1][j - 1] , dp[i][j] + ToLeft[i] + 2 * t * i);//move back from i.
            Min(dp[i + 1][j] , dp[i][j] + StayRight[i]);//continue forward.
            Min(dp[i + 1][j + 1] , dp[i][j] + ToRight[i] - 2 * t * i);// later return to i.
            if(j > 0)Min(dp[i + 1][j] , dp[i][j] + StayLeft[i]);//continue backward , must be in a path going backward.(j > 0)
        }
    }
    cout << (n + 1) * t  + dp[n][0] << endl;
}

Compilation message (stderr)

stamps.cpp: In function 'int main()':
stamps.cpp:29:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   29 |   freopen(taskname".INP", "r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
stamps.cpp:30:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   30 |   freopen(taskname".OUT", "w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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