Submission details
Task:Stack
Sender:AVL-tiimi
Submission time:2017-09-05 18:31:27 +0300
Language:C++
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.03 sdetails
#2ACCEPTED0.03 sdetails
#3ACCEPTED0.04 sdetails
#40.04 sdetails
#5ACCEPTED0.05 sdetails
#60.05 sdetails
#7ACCEPTED0.02 sdetails
#8ACCEPTED0.04 sdetails
#9ACCEPTED0.04 sdetails
#10ACCEPTED0.04 sdetails
#11ACCEPTED0.07 sdetails
#12ACCEPTED0.06 sdetails
#13ACCEPTED0.13 sdetails
#14ACCEPTED0.12 sdetails
#15ACCEPTED0.08 sdetails
#16ACCEPTED0.07 sdetails
#17ACCEPTED0.06 sdetails
#18ACCEPTED0.10 sdetails
#19ACCEPTED0.05 sdetails
#20ACCEPTED0.11 sdetails
#21ACCEPTED0.06 sdetails
#22ACCEPTED0.05 sdetails
#23ACCEPTED0.10 sdetails
#24ACCEPTED0.10 sdetails
#25ACCEPTED0.08 sdetails
#26ACCEPTED0.13 sdetails
#27ACCEPTED0.12 sdetails
#28ACCEPTED0.12 sdetails
#29ACCEPTED0.11 sdetails
#30ACCEPTED0.11 sdetails

Code

#include <iostream> 
#include <algorithm> 
#include <map>
using namespace std;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  int t[n];
  for (int i = 0; i < n; ++i) cin >> t[i];
  sort(t, t+n);
  map<long, int> sh;
  int result = 0;
  for (int i = 0; i < n; ++i) {
    auto it = sh.lower_bound(t[i]);
    if (it == sh.begin()) {
      sh[t[i]] = max(sh[t[i]], 1);
      continue;
    }
    it--;
    sh[it->first+t[i]] = max(sh[it->first+t[i]], it->second+1);
    result = max(result, it->second+1);
  }
  cout << result << endl;
}

Test details

Test 1

Verdict: ACCEPTED

input
4
424238336 25202363 35005212 14...

correct output
4

user output
4

Test 2

Verdict: ACCEPTED

input
10
59961394 38664371 42999171 110...

correct output
6

user output
6

Test 3

Verdict: ACCEPTED

input
3
515530020 713258271 409959709

correct output
2

user output
2

Test 4

Verdict:

input
1
200747797

correct output
1

user output
0

Test 5

Verdict: ACCEPTED

input
9
990892922 982275857 971899229 ...

correct output
2

user output
2

Test 6

Verdict:

input
1
889023312

correct output
1

user output
0

Test 7

Verdict: ACCEPTED

input
2
308044879 569229321

correct output
2

user output
2

Test 8

Verdict: ACCEPTED

input
5
143408283 7684931 58657200 251...

correct output
4

user output
4

Test 9

Verdict: ACCEPTED

input
10
57467588 70575322 1229905 3075...

correct output
7

user output
7

Test 10

Verdict: ACCEPTED

input
6
964445885 857962505 982936785 ...

correct output
2

user output
2

Test 11

Verdict: ACCEPTED

input
38047
886086991 795519126 932026305 ...

correct output
3

user output
3

Test 12

Verdict: ACCEPTED

input
29893
833449327 923424589 952900934 ...

correct output
3

user output
3

Test 13

Verdict: ACCEPTED

input
88014
969447982 807930869 808380133 ...

correct output
4

user output
4

Test 14

Verdict: ACCEPTED

input
99344
906117126 897804011 971671147 ...

correct output
5

user output
5

Test 15

Verdict: ACCEPTED

input
62314
462021267 934863316 993370481 ...

correct output
7

user output
7

Test 16

Verdict: ACCEPTED

input
27694
240116018 868610758 137701075 ...

correct output
17

user output
17

Test 17

Verdict: ACCEPTED

input
34371
186030714 160126823 461672475 ...

correct output
18

user output
18

Test 18

Verdict: ACCEPTED

input
86349
656924271 917573388 778539545 ...

correct output
4

user output
4

Test 19

Verdict: ACCEPTED

input
20251
113931818 172902112 9762002 20...

correct output
19

user output
19

Test 20

Verdict: ACCEPTED

input
83687
886215461 933101589 797491836 ...

correct output
5

user output
5

Test 21

Verdict: ACCEPTED

input
8844
872792510 862670778 832399887 ...

correct output
3

user output
3

Test 22

Verdict: ACCEPTED

input
3878
17470245 12329636 76365192 931...

correct output
15

user output
15

Test 23

Verdict: ACCEPTED

input
88281
903739625 918958000 971351153 ...

correct output
3

user output
3

Test 24

Verdict: ACCEPTED

input
76036
45705320 20298487 219558827 46...

correct output
19

user output
19

Test 25

Verdict: ACCEPTED

input
25005
723905756 832888029 891663363 ...

correct output
4

user output
4

Test 26

Verdict: ACCEPTED

input
100000
952154293 749159333 729781909 ...

correct output
6

user output
6

Test 27

Verdict: ACCEPTED

input
100000
637326184 951424615 882073847 ...

correct output
5

user output
5

Test 28

Verdict: ACCEPTED

input
100000
43852364 62939153 26979371 730...

correct output
19

user output
19

Test 29

Verdict: ACCEPTED

input
100000
546749347 33431699 27660950 14...

correct output
20

user output
20

Test 30

Verdict: ACCEPTED

input
100000
729474052 612434893 922262202 ...

correct output
6

user output
6