oj.uz

Submission #361658

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

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

# Verdict Execution time Memory Grader output
1 Correct 23 ms 35692 KB Output is correct
2 Correct 23 ms 35692 KB Output is correct
3 Correct 23 ms 35692 KB Output is correct
4 Correct 23 ms 35692 KB Output is correct
5 Correct 23 ms 35692 KB Output is correct
6 Correct 23 ms 35692 KB Output is correct
7 Correct 23 ms 35692 KB Output is correct
8 Correct 25 ms 35692 KB Output is correct
9 Correct 23 ms 35692 KB Output is correct
10 Correct 23 ms 35692 KB Output is correct
11 Correct 23 ms 35820 KB Output is correct
12 Correct 28 ms 35692 KB Output is correct
13 Correct 27 ms 35692 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 35692 KB Output is correct
2 Correct 22 ms 35692 KB Output is correct
3 Correct 23 ms 35692 KB Output is correct
4 Correct 23 ms 35692 KB Output is correct
5 Correct 23 ms 35692 KB Output is correct
6 Correct 23 ms 35692 KB Output is correct
7 Correct 23 ms 35692 KB Output is correct
8 Correct 24 ms 35692 KB Output is correct
9 Correct 23 ms 35692 KB Output is correct
10 Correct 24 ms 35820 KB Output is correct
11 Correct 23 ms 35692 KB Output is correct
12 Correct 23 ms 35692 KB Output is correct
13 Correct 23 ms 35692 KB Output is correct
14 Correct 23 ms 35692 KB Output is correct
15 Correct 23 ms 35692 KB Output is correct
16 Correct 23 ms 35692 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 35856 KB Output is correct
2 Correct 22 ms 35692 KB Output is correct
3 Correct 82 ms 35820 KB Output is correct
4 Correct 55 ms 35840 KB Output is correct
5 Correct 60 ms 35820 KB Output is correct
6 Correct 35 ms 35820 KB Output is correct
7 Correct 29 ms 35820 KB Output is correct
8 Correct 64 ms 35820 KB Output is correct
9 Correct 60 ms 35820 KB Output is correct
10 Correct 61 ms 35840 KB Output is correct
11 Correct 64 ms 35820 KB Output is correct
12 Correct 60 ms 35820 KB Output is correct
13 Correct 60 ms 35820 KB Output is correct
14 Correct 60 ms 35820 KB Output is correct
15 Correct 61 ms 35820 KB Output is correct
16 Correct 63 ms 35820 KB Output is correct
17 Correct 66 ms 35948 KB Output is correct