Submission #2074687


Source Code Expand

Copy
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<(n);i++)
#define loop(i,a,n) for(i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef pair<int,int> pii;

int dp[5005][5005];

int main(void) {
  int i,j,k;
  int n,x;
  cin>>n>>x;

  vi t(n+1);
  t[0]=-x;
  rep(i,n)cin>>t[i+1];

  rep(i,n+1)rep(j,n+1)dp[i][j]=-1;

  dp[0][0]=0;
  rep(i,n)rep(j,n)if(dp[i][j]>=0){
    for(k=i+1;k<=n;k++)
      dp[k][j+1]=max(dp[k][j+1],dp[i][j]+min(x,t[k]-t[i]));
  }

  for(j=1;j<=n;j++){
    int ans=0;
    rep(i,n+1)if(dp[i][j]>=0)ans=max(ans,dp[i][j]);
    cout<<ans<<endl;
  }

}

Submission Info

Submission Time
Task D - すぬけそだて――トレーニング――
User rika0384
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1065 Byte
Status

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt
All 0 / 500 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt
02.txt
03.txt
04.txt
05.txt
06.txt
07.txt
08.txt
09.txt
10.txt
11.txt
12.txt
13.txt
14.txt
15.txt
16.txt
17.txt
18.txt
19.txt
20.txt
21.txt
22.txt
23.txt
24.txt
25.txt
26.txt
27.txt
28.txt
29.txt
30.txt
31.txt
32.txt
33.txt
34.txt
35.txt
36.txt
37.txt
38.txt
39.txt
40.txt
41.txt 1 ms 256 KB
42.txt 1 ms 256 KB
43.txt 1 ms 256 KB
44.txt 1 ms 256 KB
s1.txt 1 ms 256 KB
s2.txt 1 ms 256 KB
s3.txt 1 ms 256 KB