Submission #1990617
Source Code Expand
#include <iostream> #include <string> #include <vector> #include <algorithm> #include <queue> #include <set> #include <map> using namespace std; typedef long long ll; int N; int M; ll t[10010]; ll dp[3][5010][2]; int main() { for (int i = 0; i < 3; i++) { for (int j = 0; j < 5010; j++) { dp[i][j][0] = 10000000000000000LL; dp[i][j][1] = 10000000000000000LL; } } dp[0][0][0] = 0; dp[0][0][1] = 1; cin >> N; M = N / 2; for (int i = 1; i <= N - 1; i++) { cin >> t[i]; } for (int i = 1; i <= N; i++) { for (int j = 0; j <= M; j++) { dp[(i) % 3 ][j][0] = 10000000000000000LL; dp[(i) % 3 ][j][1] = 10000000000000000LL; if (j > 0) dp[(i) % 3 ][j][0] = min(dp[(i) % 3 ][j][0], dp[(i - 1) % 3 ][j - 1][0]); dp[(i) % 3 ][j][1] = min(dp[(i) % 3 ][j][1], dp[(i - 1) % 3 ][j][1]); if (j > 0) { dp[(i) % 3 ][j][0] = min(dp[(i) % 3 ][j][0], dp[(i - 1) % 3 ][j - 1][0] + t[i]); dp[(i) % 3 ][j][1] = min(dp[(i) % 3 ][j][1], dp[(i - 1) % 3 ][j - 1][0] + t[i]); } dp[(i) % 3 ][j][0] = min(dp[(i) % 3 ][j][0], dp[(i - 1) % 3 ][j][1] + t[i]); dp[(i) % 3 ][j][1] = min(dp[(i) % 3 ][j][1], dp[(i - 1) % 3 ][j][1] + t[i]); } } cout << min(dp[(N) % 3 ][M][0], dp[(N) % 3 ][M][1]) << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - お菓子の分割 |
User | niuez |
Language | C++14 (GCC 5.4.1) |
Score | 20 |
Code Size | 1545 Byte |
Status | AC |
Exec Time | 254 ms |
Memory | 512 KB |
Judge Result
Set Name | set01 | set02 | set03 | set04 | set05 | set06 | set07 | set08 | set09 | set10 | ||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 2 / 2 | 2 / 2 | 2 / 2 | 2 / 2 | 2 / 2 | 2 / 2 | 2 / 2 | 2 / 2 | 2 / 2 | 2 / 2 | ||||||||||||||||||||
Status |
|
|
|
|
|
|
|
|
|
|
Set Name | Test Cases |
---|---|
set01 | data1 |
set02 | data2 |
set03 | data3 |
set04 | data4 |
set05 | data5 |
set06 | data6 |
set07 | data7 |
set08 | data8 |
set09 | data9 |
set10 | data10 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
data1 | AC | 65 ms | 512 KB |
data10 | AC | 254 ms | 512 KB |
data11 | AC | 254 ms | 512 KB |
data12 | AC | 254 ms | 512 KB |
data13 | AC | 254 ms | 512 KB |
data14 | AC | 254 ms | 512 KB |
data15 | AC | 254 ms | 512 KB |
data16 | AC | 254 ms | 512 KB |
data17 | AC | 254 ms | 512 KB |
data18 | AC | 254 ms | 512 KB |
data19 | AC | 254 ms | 512 KB |
data2 | AC | 254 ms | 512 KB |
data20 | AC | 254 ms | 512 KB |
data3 | AC | 1 ms | 512 KB |
data4 | AC | 1 ms | 512 KB |
data5 | AC | 1 ms | 512 KB |
data6 | AC | 1 ms | 512 KB |
data7 | AC | 65 ms | 512 KB |
data8 | AC | 164 ms | 512 KB |
data9 | AC | 206 ms | 512 KB |