Submission #00003
ソースコード
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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | #include <bits/stdc++.h> using namespace std; #define __ <<" "<< #define ___ <<" " #define bash push_back #define ALL(x) x.begin(),x.end() #define int long long struct IoSetup { IoSetup() { cin.tie(0); ios::sync_with_stdio( false ); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); } }IoSetup; typedef long long ll; typedef pair < int , int > pii; static const signed int INF = 0x3f3f3f3f; static const signed long long LINF = 0x3f3f3f3f3f3f3f3fLL; static const signed int SMOD = 1000000007; static const signed int NMOD = 998244353; static const signed int dx[]={1,0,-1,0,1,1,-1,-1}; static const signed int dy[]={0,-1,0,1,-1,1,-1,1}; bool inside( int x, int y, int w, int h){ return (x>=0 && y>=0 && x<w && y<h);} template < class T> bool chmax(T &a, const T&b){ if (a<b) return (a=b,1); return 0;} template < class T> bool chmin(T &a, const T&b){ if (b<a) return (a=b,1); return 0;} int n, m , k; int a[20200]; int mem[20200]; int dfs( int i) { if (i==n) return 0; if (i > n) return LINF; if (~mem[i]) return mem[i]; mem[i] =LINF; int mini = a[i], maxi = a[i]; for ( int l = 0; l < m; l++) { if (l+i > n) break ; chmax(maxi,a[i+l]); chmin(mini,a[i+l]); chmin(mem[i], dfs(i+l+1) + k + (maxi-mini)*(l+1)); } return mem[i]; } signed main() { cin >> n >> m >> k; for ( int i = 0; i < n; i++) { cin >> a[i]; } int ans = LINF; memset (mem,-1, sizeof (mem)); cout <<dfs(0) << endl; return 0; } |
ステータス
項目 | データ |
---|---|
問題 | 0003 - オレンジの出荷 (Oranges) |
ユーザー名 | ei1821 |
投稿日時 | 2019-12-16 17:38:52 |
言語 | C++14 |
状態 | Accepted |
得点 | 100 |
ソースコード長 | 1542 Byte |
最大実行時間 | 91 ms |
最大メモリ使用量 | 4956 KB |
セット
セット | 得点 | Cases | |
---|---|---|---|
1 | Subtask1 | 20 / 20 | 01-*, sample-* |
2 | Subtask2 | 50 / 50 | 01-*, 02-*, sample-* |
3 | Subtask3 | 30 / 30 | * |
テストケース
ファイル名 | 状態 | 実行時間 | メモリ使用量 | # | ||
---|---|---|---|---|---|---|
01-01.txt | AC | 40 ms | 860 KB |
1
|
2
|
3
|
01-02.txt | AC | 25 ms | 776 KB |
1
|
2
|
3
|
01-03.txt | AC | 21 ms | 700 KB |
1
|
2
|
3
|
01-04.txt | AC | 20 ms | 876 KB |
1
|
2
|
3
|
01-05.txt | AC | 38 ms | 804 KB |
1
|
2
|
3
|
01-06.txt | AC | 20 ms | 852 KB |
1
|
2
|
3
|
01-07.txt | AC | 15 ms | 652 KB |
1
|
2
|
3
|
01-08.txt | AC | 20 ms | 576 KB |
1
|
2
|
3
|
01-09.txt | AC | 22 ms | 756 KB |
1
|
2
|
3
|
01-10.txt | AC | 24 ms | 808 KB |
1
|
2
|
3
|
01-11.txt | AC | 19 ms | 728 KB |
1
|
2
|
3
|
01-12.txt | AC | 23 ms | 780 KB |
1
|
2
|
3
|
01-13.txt | AC | 23 ms | 832 KB |
1
|
2
|
3
|
01-14.txt | AC | 19 ms | 884 KB |
1
|
2
|
3
|
01-15.txt | AC | 19 ms | 812 KB |
1
|
2
|
3
|
02-01.txt | AC | 22 ms | 992 KB |
2
|
3
|
|
02-02.txt | AC | 22 ms | 936 KB |
2
|
3
|
|
02-03.txt | AC | 32 ms | 1008 KB |
2
|
3
|
|
02-04.txt | AC | 17 ms | 952 KB |
2
|
3
|
|
02-05.txt | AC | 18 ms | 900 KB |
2
|
3
|
|
02-06.txt | AC | 26 ms | 976 KB |
2
|
3
|
|
02-07.txt | AC | 27 ms | 1048 KB |
2
|
3
|
|
02-08.txt | AC | 22 ms | 1124 KB |
2
|
3
|
|
02-09.txt | AC | 30 ms | 1068 KB |
2
|
3
|
|
02-10.txt | AC | 17 ms | 1144 KB |
2
|
3
|
|
02-11.txt | AC | 23 ms | 1216 KB |
2
|
3
|
|
02-12.txt | AC | 22 ms | 1156 KB |
2
|
3
|
|
02-13.txt | AC | 44 ms | 1228 KB |
2
|
3
|
|
02-14.txt | AC | 33 ms | 1172 KB |
2
|
3
|
|
02-15.txt | AC | 22 ms | 1252 KB |
2
|
3
|
|
03-01.txt | AC | 42 ms | 2344 KB |
3
|
||
03-02.txt | AC | 67 ms | 2588 KB |
3
|
||
03-03.txt | AC | 63 ms | 2708 KB |
3
|
||
03-04.txt | AC | 81 ms | 2952 KB |
3
|
||
03-05.txt | AC | 46 ms | 3320 KB |
3
|
||
03-06.txt | AC | 75 ms | 3560 KB |
3
|
||
03-07.txt | AC | 69 ms | 3672 KB |
3
|
||
03-08.txt | AC | 64 ms | 3780 KB |
3
|
||
03-09.txt | AC | 76 ms | 4020 KB |
3
|
||
03-10.txt | AC | 62 ms | 4260 KB |
3
|
||
03-11.txt | AC | 62 ms | 4372 KB |
3
|
||
03-12.txt | AC | 71 ms | 4360 KB |
3
|
||
03-13.txt | AC | 45 ms | 4856 KB |
3
|
||
03-14.txt | AC | 91 ms | 4844 KB |
3
|
||
03-15.txt | AC | 54 ms | 4956 KB |
3
|
||
sample-01.txt | AC | 20 ms | 3924 KB |
1
|
2
|
3
|
sample-02.txt | AC | 22 ms | 3972 KB |
1
|
2
|
3
|
sample-03.txt | AC | 18 ms | 3900 KB |
1
|
2
|
3
|
sample-04.txt | AC | 21 ms | 3956 KB |
1
|
2
|
3
|