Advertisement
Guest User

Untitled

a guest
Jan 17th, 2018
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.33 KB | None | 0 0
  1. #include<cstdio>
  2. #include<cstring>
  3. #include<vector>
  4. #include<algorithm>
  5. #define f first
  6. #define s second
  7. #define PRIM 23
  8. using namespace std;
  9. vector<pair<int,int> > points[1002]; ///pair<punctaj_curent, step>
  10. int i, j, n, len, val, mx, sol, best;
  11. char rez[35][1002], s[35];
  12. bool ok;
  13. int lastpoz(int poz){
  14. vector<pair<int,int> >::iterator it;
  15. int sum=0;
  16. for (it=points[poz].begin();it!=points[poz].end();++it) {
  17. sum+=(*it).f;
  18. if (sum>=mx) return (*it).s;
  19. }
  20. return 999999999;
  21. }
  22. int main(){
  23. //freopen("in.txt","r",stdin);
  24. //freopen("out.txt","w",stdout);
  25. scanf("%d\n", &n);
  26. len=0; mx=0;
  27. for (i=1;i<=n;++i) {
  28. scanf("%s %d\n", s, &val);
  29. ok=true;
  30. for (j=1;j<=len;++j) {
  31. if (strcmp(s, rez[j])==0) {
  32. points[j].push_back(make_pair((points[j].back()).f+val, i));
  33. ok=false; break;
  34. }
  35. }
  36. if (ok) {
  37. strcpy(rez[++len], s);
  38. points[len].push_back(make_pair(val, i));
  39. }
  40. }
  41. for (i=1;i<=len;i++) {
  42. if ((points[i].back()).f>mx) {
  43. mx=(points[i].back()).f; sol=i; best=lastpoz(i);
  44. }
  45. else if (((points[i].back()).f==mx)&&(lastpoz(i)<best)) {
  46. mx=(points[i].back()).f; sol=i; best=lastpoz(i);
  47. }
  48. }
  49. printf("%s\n", rez[sol]);
  50. return 0;
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement