Submission #201025

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
201025	2020-02-09 06:26:16	gs14004	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	357 ms	516728 KiB

ho_t3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using pi = pair<int, int>;
using lint = long long;
const int MAXN = 404;
int n, l;
pi a[MAXN];
lint dp[MAXN][MAXN][MAXN / 2][2];
lint dist(int x, int y){ return abs(a[x].first - a[y].first); }
int main(){
  cin >> n >> l;
  for(int i=1; i<=n; i++) cin >> a[i+n].first;
  for(int i=1; i<=n; i++) cin >> a[i+n].second;
  for(int i=0; i<n; i++) a[i] = pi(a[i+n+1].first - l, a[i+n+1].second);
  a[n] = pi(0, 0);
  memset(dp, 0x3f, sizeof(dp));
  dp[n][n][0][0] = dp[n][n][0][1] = 0;
  int dap = 0;
  for(int i=1; i<=n; i++){
    for(int j=0; j+i<=2*n; j++){
      for(int k=0; k<=i; k++){
        dp[j][j + i][k][0] = min(dp[j+1][j+i][k][0] + dist(j+1, j), dp[j+1][j+i][k][1] + dist(j+i, j));
        if(k > 0 && dp[j + 1][j + i][k - 1][0] + dist(j+1, j) <= a[j].second){
          dp[j][j + i][k][0] = min(dp[j][j + i][k][0], dp[j+1][j+i][k-1][0] + dist(j+1, j));
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75