Submission #639642

#	Time	Username	Problem	Language	Result	Execution time	Memory
639642		teesla	Rabbit Carrot (LMIO19_triusis)	C++14	63 / 100	103 ms	118604 KiB

triusis

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e4;

int v[maxn],dp[maxn][maxn];
int n,m;
int main(){
	cin >> n>> m;

	for(int i=0; i<n; i++)cin >> v[i+1];
	for(int i=0; i<=n; i++)for(int j=0; j<=n; j++) dp[i][j]=-1;
	for(int i=0; i<=n; i++) dp[0][i]=0;

	for(int i=1; i<=n; i++) for(int j=0; j<=n; j++){
		int npega=dp[i-1][j];
		if(npega==-1) npega=-1;
		else if(npega>=v[i])npega=v[i];
		else if(npega+m<v[i])npega=-1;
		else npega=v[i];
		int pega;
		if(j==0)pega=-1;
		else{
			pega=dp[i-1][j-1];
			if(pega==-1) pega=-1;
			else if(pega>=v[i]) pega=pega+m;
			else pega=pega+m;
		}
		dp[i][j]=max(pega,npega);
	}

	for(int i=0; i<=n; i++){
		if(dp[n][i]!=-1){
			cout << i <<endl;
			break;
		}
	}
	return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 28 / 28
• Subtask 4: 0 / 37