Submission details
Task:Stack
Sender:AVL-tiimi
Submission time:2017-09-05 19:24:52 +0300
Language:C++
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.05 sdetails
#2ACCEPTED0.05 sdetails
#3ACCEPTED0.05 sdetails
#4ACCEPTED0.04 sdetails
#5ACCEPTED0.03 sdetails
#6ACCEPTED0.06 sdetails
#7ACCEPTED0.04 sdetails
#8ACCEPTED0.03 sdetails
#90.04 sdetails
#10ACCEPTED0.04 sdetails
#110.05 sdetails
#120.04 sdetails
#130.06 sdetails
#140.06 sdetails
#150.06 sdetails
#160.04 sdetails
#170.06 sdetails
#180.06 sdetails
#190.05 sdetails
#200.05 sdetails
#210.03 sdetails
#220.04 sdetails
#230.06 sdetails
#240.06 sdetails
#250.05 sdetails
#260.07 sdetails
#270.05 sdetails
#280.08 sdetails
#290.07 sdetails
#300.06 sdetails

Code

#include <iostream> 
#include <algorithm> 
#include <map>
#include <vector>

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);
  long stsum = 0;
  int sth = 0, R = 0;
  for (int i = 0; i < n; ++i) {
    if (!stsum) stsum += t[i], sth = 1;
    else {
      if (stsum < t[i]) {
        stsum += t[i];
        sth++;
      } else {
        stsum -= t[i-1];
        stsum += t[i];
      }
    }
    if (sth > R) R = sth;
  }
  cout << R << endl;
  // 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: ACCEPTED

input
1
200747797

correct output
1

user output
1

Test 5

Verdict: ACCEPTED

input
9
990892922 982275857 971899229 ...

correct output
2

user output
2

Test 6

Verdict: ACCEPTED

input
1
889023312

correct output
1

user output
1

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:

input
10
57467588 70575322 1229905 3075...

correct output
7

user output
6

Test 10

Verdict: ACCEPTED

input
6
964445885 857962505 982936785 ...

correct output
2

user output
2

Test 11

Verdict:

input
38047
886086991 795519126 932026305 ...

correct output
3

user output
2

Test 12

Verdict:

input
29893
833449327 923424589 952900934 ...

correct output
3

user output
2

Test 13

Verdict:

input
88014
969447982 807930869 808380133 ...

correct output
4

user output
2

Test 14

Verdict:

input
99344
906117126 897804011 971671147 ...

correct output
5

user output
2

Test 15

Verdict:

input
62314
462021267 934863316 993370481 ...

correct output
7

user output
2

Test 16

Verdict:

input
27694
240116018 868610758 137701075 ...

correct output
17

user output
5

Test 17

Verdict:

input
34371
186030714 160126823 461672475 ...

correct output
18

user output
6

Test 18

Verdict:

input
86349
656924271 917573388 778539545 ...

correct output
4

user output
2

Test 19

Verdict:

input
20251
113931818 172902112 9762002 20...

correct output
19

user output
7

Test 20

Verdict:

input
83687
886215461 933101589 797491836 ...

correct output
5

user output
2

Test 21

Verdict:

input
8844
872792510 862670778 832399887 ...

correct output
3

user output
2

Test 22

Verdict:

input
3878
17470245 12329636 76365192 931...

correct output
15

user output
5

Test 23

Verdict:

input
88281
903739625 918958000 971351153 ...

correct output
3

user output
2

Test 24

Verdict:

input
76036
45705320 20298487 219558827 46...

correct output
19

user output
5

Test 25

Verdict:

input
25005
723905756 832888029 891663363 ...

correct output
4

user output
2

Test 26

Verdict:

input
100000
952154293 749159333 729781909 ...

correct output
6

user output
2

Test 27

Verdict:

input
100000
637326184 951424615 882073847 ...

correct output
5

user output
2

Test 28

Verdict:

input
100000
43852364 62939153 26979371 730...

correct output
19

user output
5

Test 29

Verdict:

input
100000
546749347 33431699 27660950 14...

correct output
20

user output
6

Test 30

Verdict:

input
100000
729474052 612434893 922262202 ...

correct output
6

user output
2