Task: | Maalarit |
Sender: | Pohjantahti |
Submission time: | 2016-10-05 17:51:32 +0300 |
Language: | C++ |
Status: | READY |
Result: | 12 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 12 |
#2 | RUNTIME ERROR | 0 |
#3 | RUNTIME ERROR | 0 |
#4 | RUNTIME ERROR | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.06 s | 1 | details |
#2 | ACCEPTED | 0.06 s | 1 | details |
#3 | ACCEPTED | 0.24 s | 1 | details |
#4 | ACCEPTED | 0.06 s | 1 | details |
#5 | ACCEPTED | 0.05 s | 1 | details |
#6 | ACCEPTED | 0.05 s | 1 | details |
#7 | RUNTIME ERROR | 0.16 s | 2 | details |
#8 | RUNTIME ERROR | 0.15 s | 2 | details |
#9 | RUNTIME ERROR | 0.14 s | 2 | details |
#10 | RUNTIME ERROR | 0.15 s | 2 | details |
#11 | RUNTIME ERROR | 0.15 s | 2 | details |
#12 | ACCEPTED | 0.06 s | 2 | details |
#13 | RUNTIME ERROR | 0.15 s | 3 | details |
#14 | RUNTIME ERROR | 0.15 s | 3 | details |
#15 | RUNTIME ERROR | 0.14 s | 3 | details |
#16 | RUNTIME ERROR | 0.16 s | 3 | details |
#17 | RUNTIME ERROR | 0.16 s | 3 | details |
#18 | ACCEPTED | 0.06 s | 3 | details |
#19 | RUNTIME ERROR | 0.20 s | 4 | details |
#20 | RUNTIME ERROR | 0.20 s | 4 | details |
#21 | RUNTIME ERROR | 0.19 s | 4 | details |
#22 | RUNTIME ERROR | 0.20 s | 4 | details |
#23 | RUNTIME ERROR | 0.18 s | 4 | details |
#24 | TIME LIMIT EXCEEDED | -- | 4 | details |
Code
#include <iostream>#include <vector>#include <utility>#include <queue>#include <algorithm>#include <cstring>// #include <fstream>using namespace std;typedef long long ll;typedef pair<int, int> ii;typedef vector<int> vi;const int INF = 1000000000;int n;vi h;int p[100005];int minCost = INF;int nPtrs;int ptrs[15];bool place(int i, int val) {if (i > 0 && p[i - 1] == val) return false;return true;}int getCost(int end) {int cs[15];memset(cs, 0, sizeof cs);int curMinCost = 0;for (int i = 0; i < end; ++i) {int cP = p[i];if (cs[cP] == 0) {cs[cP] = h[i];curMinCost += cs[cP];}else if (h[i] > cs[cP]) {curMinCost -= cs[cP];curMinCost += h[i];cs[cP] = h[i];}}return curMinCost;}void cs(int cur) {if (cur == n) {int cs[15];memset(cs, 0, sizeof cs);int curNPtrs = 0;int curMinCost = 0;for (int i = 0; i < n; ++i) {// who painted current plankint cP = p[i];if (cs[cP] == 0) {cs[cP] = h[i];curMinCost += cs[cP];++curNPtrs;}else if (h[i] > cs[cP]) {curMinCost -= cs[cP];curMinCost += h[i];cs[cP] = h[i];}}if (curMinCost < minCost) {minCost = curMinCost;nPtrs = curNPtrs;for (int i = 0; i < n; ++i) {ptrs[i] = p[i];}}return;}if (getCost(cur) >= minCost) return; // prunefor (int i = 1; i < n + 1; ++i) {if (place(cur, i)) { // values 1..np[cur] = i;cs(cur + 1);}}}int main() {/*ifstream in("input.txt");cin.rdbuf(in.rdbuf());*/cin >> n;for (int i = 0; i < n; ++i) {int cH;cin >> cH;h.push_back(cH);}p[0] = 1;cs(1);cout << minCost << " " << nPtrs << endl;for (int i = 0; i < n; ++i) {cout << ptrs[i];if (i != n - 1) cout << " ";}cout << endl;return 0;}
Test details
Test 1
Group: 1
Verdict: ACCEPTED
input |
---|
10 22 54 3 91 69 90 40 29 83 71 |
correct output |
---|
174 3 2 1 2 1 2 1 2 1 2 1 |
user output |
---|
174 2 1 2 1 2 1 2 1 2 1 2 |
Test 2
Group: 1
Verdict: ACCEPTED
input |
---|
10 49 3 96 38 90 18 92 74 83 1 |
correct output |
---|
170 3 1 2 1 2 1 2 1 2 1 2 |
user output |
---|
170 2 1 2 1 2 1 2 1 2 1 2 |
Test 3
Group: 1
Verdict: ACCEPTED
input |
---|
10 46 3 41 30 16 17 12 93 80 81 |
correct output |
---|
173 3 2 1 2 1 2 1 2 1 2 1 |
user output |
---|
173 2 1 2 1 2 1 2 1 2 1 2 |
Test 4
Group: 1
Verdict: ACCEPTED
input |
---|
10 46 8 95 85 82 73 82 92 53 90 |
correct output |
---|
187 3 1 2 1 2 1 2 1 2 1 2 |
user output |
---|
187 2 1 2 1 2 1 2 1 2 1 2 |
Test 5
Group: 1
Verdict: ACCEPTED
input |
---|
10 41 18 61 59 40 96 5 2 74 38 |
correct output |
---|
159 3 2 1 2 1 2 1 2 3 1 2 |
user output |
---|
159 3 1 2 1 2 1 2 1 3 2 1 |
Test 6
Group: 1
Verdict: ACCEPTED
input |
---|
10 1 1 1 1 1 1 1 1 1 1 |
correct output |
---|
2 3 2 1 2 1 2 1 2 1 2 1 |
user output |
---|
2 2 1 2 1 2 1 2 1 2 1 2 |
Test 7
Group: 2
Verdict: RUNTIME ERROR
input |
---|
100 1 39 94 5 24 84 84 10 78 61 38... |
correct output |
---|
193 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
(empty) |
Test 8
Group: 2
Verdict: RUNTIME ERROR
input |
---|
100 31 73 18 88 49 28 66 5 32 48 9... |
correct output |
---|
199 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
user output |
---|
(empty) |
Test 9
Group: 2
Verdict: RUNTIME ERROR
input |
---|
100 45 56 36 60 31 10 23 79 29 17 ... |
correct output |
---|
198 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
(empty) |
Test 10
Group: 2
Verdict: RUNTIME ERROR
input |
---|
100 1 77 70 62 21 68 40 54 90 62 1... |
correct output |
---|
194 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
(empty) |
Test 11
Group: 2
Verdict: RUNTIME ERROR
input |
---|
100 4 47 41 81 56 64 12 10 20 100 ... |
correct output |
---|
189 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
user output |
---|
(empty) |
Test 12
Group: 2
Verdict: ACCEPTED
input |
---|
10 1 1 1 1 1 1 1 1 1 1 |
correct output |
---|
2 3 2 1 2 1 2 1 2 1 2 1 |
user output |
---|
2 2 1 2 1 2 1 2 1 2 1 2 |
Test 13
Group: 3
Verdict: RUNTIME ERROR
input |
---|
100 256160448 813097800 167146270 ... |
correct output |
---|
1929869257 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
(empty) |
Test 14
Group: 3
Verdict: RUNTIME ERROR
input |
---|
100 520002672 3542567 24668528 959... |
correct output |
---|
1946957555 3 1 2 3 1 2 1 2 1 2 1 2 1 2 1 2 ... |
user output |
---|
(empty) |
Test 15
Group: 3
Verdict: RUNTIME ERROR
input |
---|
100 483158423 780224665 844754665 ... |
correct output |
---|
1959373560 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
user output |
---|
(empty) |
Test 16
Group: 3
Verdict: RUNTIME ERROR
input |
---|
100 969647264 128558017 889036329 ... |
correct output |
---|
1997942264 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
user output |
---|
(empty) |
Test 17
Group: 3
Verdict: RUNTIME ERROR
input |
---|
100 745018527 400495893 635468795 ... |
correct output |
---|
1961391143 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
user output |
---|
(empty) |
Test 18
Group: 3
Verdict: ACCEPTED
input |
---|
10 1 1 1 1 1 1 1 1 1 1 |
correct output |
---|
2 3 2 1 2 1 2 1 2 1 2 1 |
user output |
---|
2 2 1 2 1 2 1 2 1 2 1 2 |
Test 19
Group: 4
Verdict: RUNTIME ERROR
input |
---|
100000 197349274 775463806 263930657 ... |
correct output |
---|
1999942635 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
(empty) |
Test 20
Group: 4
Verdict: RUNTIME ERROR
input |
---|
100000 102296405 34648120 320393597 9... |
correct output |
---|
1999930943 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
user output |
---|
(empty) |
Test 21
Group: 4
Verdict: RUNTIME ERROR
input |
---|
100000 781254921 418252056 502363453 ... |
correct output |
---|
1999987794 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
(empty) |
Test 22
Group: 4
Verdict: RUNTIME ERROR
input |
---|
100000 849784881 230439009 455097426 ... |
correct output |
---|
1999979439 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
(empty) |
Test 23
Group: 4
Verdict: RUNTIME ERROR
input |
---|
100000 851456132 13422224 537539701 4... |
correct output |
---|
1999948226 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
(empty) |
Test 24
Group: 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
2 3 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 ... |
user output |
---|
(empty) |