Submission #1444146
Source Code Expand
#include <iostream> #include <stdio.h> #include <string> #include <cstdlib> #include <cmath> #include <algorithm> #include <string.h> #include <queue> #include <stack> #include <set> #include <map> #include <time.h> #define _USE_MATH_DEFINES #define LL long long using namespace std; const double PI = acos(-1.0); int max_num(int ary[],int length) { int max = ary[0]; for (int i = 1; i < length; i++) if (max < ary[i]) max = ary[i]; return max; } int max_ord(int ary[], int length) { int max; max = max_num(ary, length); for (int i = 0; i < length; i++) { if (ary[i] == max) return i; } return -1; } int min_num(int ary[], int length) { int min = ary[0]; for (int i = 1; i < length; i++) if (min > ary[i]) min = ary[i]; return min; } int min_ord(int ary[], int length) { int min; min = min_num(ary, length); for (int i = 0; i < length; i++) { if (ary[i] == min) return i; } return -1; } int n, a[100000]; bool done[100000][1000]; int memo[100000][1000]; int dp(int i, int c) { if (done[i][c]) return memo[i][c]; int res; if (i == n - 1) res = c; else if (i == n - 2) res = dp(i + 1, abs(a[i] - a[i + 1])) + c; else { int res1, res2; res1 = dp(i + 1, abs(a[i] - a[i + 1])) + c; res2 = dp(i + 2, abs(a[i] - a[i + 2])) + c; res = min(res1, res2); } done[i][c] = true; memo[i][c] = res; return res; } int main() { cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; cout << dp(0, 0) << endl; }
Submission Info
Submission Time | |
---|---|
Task | C - 柱柱柱柱柱 |
User | crevette |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1521 Byte |
Status | MLE |
Exec Time | 131 ms |
Memory | 493440 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 100 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 1 ms | 2304 KB |
sample_02.txt | AC | 1 ms | 2304 KB |
sample_03.txt | AC | 2 ms | 2304 KB |
subtask1_01.txt | AC | 1 ms | 2304 KB |
subtask1_02.txt | AC | 2 ms | 2304 KB |
subtask1_03.txt | AC | 2 ms | 2304 KB |
subtask1_04.txt | MLE | 130 ms | 493440 KB |
subtask1_05.txt | MLE | 130 ms | 493312 KB |
subtask1_06.txt | MLE | 131 ms | 493312 KB |
subtask1_07.txt | MLE | 130 ms | 493312 KB |