#include <bits/stdc++.h> using namespace std; int a,t,mal,najw,l; vector<pair<int,int>>mantra[500001];//first-odpowiedz dla danego, second - na akt gownie pair<int,int>pom; bool comp(pair<int,int>p,pair<int,int>q) { if(p.first<q.first) return 1; if(p.first>q.first) return 0; if(p.second<q.second) return 0; return 1; } int szybwczyt() { char wcz=getchar(); int ret=0; bool czydz=0; while((wcz>57||wcz<48)&&wcz!='-') { wcz=getchar(); } if(wcz=='-') { wcz=getchar(); czydz=1; } while(wcz>=48&&wcz<=57) { ret=ret*10+wcz-48; wcz=getchar(); } if(czydz) return -ret; return ret; } int main() { a=szybwczyt(); mantra[0].push_back(pom); vector<pair<int,int>>test; for(int i=0;i<a;++i) { t=szybwczyt(); if(t==0) { ++mal; --i; --a; } else if(t<0) { najw=mantra[i][0].second; pom.second=mantra[i][0].second+t; pom.first=mantra[i][0].first+mal; mantra[i+1].push_back(pom); if(mantra[i][0].second>=0) { pom.second=t; pom.first=mantra[i][0].first; mantra[i+1].push_back(pom); } for(int j=1;j<mantra[i].size();++j) { if(mantra[i][j].second>najw) { najw=mantra[i][j].second; pom.second=mantra[i][j].second+t; pom.first=mantra[i][j].first+mal; mantra[i+1].push_back(pom); if(mantra[i][j].second>=0) { pom.second=t; pom.first=mantra[i][j].first; mantra[i+1].push_back(pom); } } } mal=1; sort(mantra[i+1].begin(),mantra[i+1].end(),comp); } else { l=mantra[i].size(); najw=mantra[i][0].second; pom.second=mantra[i][0].second+t; pom.first=mantra[i][0].first+mal; mantra[i+1].push_back(pom); if(mantra[i][0].second>=0) { pom.second=t; pom.first=mantra[i][0].first; mantra[i+1].push_back(pom); } for(int j=1;j<l;++j) { if(mantra[i][j].second>najw) { najw=mantra[i][j].second; if(mantra[i][j].second>=0) { pom.second=t; pom.first=mantra[i][j].first; mantra[i+1].push_back(pom); } pom.second=mantra[i][j].second+t; pom.first=mantra[i][j].first+mal; mantra[i+1].push_back(pom); } } sort(mantra[i+1].begin(),mantra[i+1].end(),comp); mal=1; } } for(int i=0;i<mantra[a].size();++i) { if(mantra[a][i].second>=0) { printf("%d",mantra[a][i].first); return 0; } } printf("-1"); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 | #include <bits/stdc++.h> using namespace std; int a,t,mal,najw,l; vector<pair<int,int>>mantra[500001];//first-odpowiedz dla danego, second - na akt gownie pair<int,int>pom; bool comp(pair<int,int>p,pair<int,int>q) { if(p.first<q.first) return 1; if(p.first>q.first) return 0; if(p.second<q.second) return 0; return 1; } int szybwczyt() { char wcz=getchar(); int ret=0; bool czydz=0; while((wcz>57||wcz<48)&&wcz!='-') { wcz=getchar(); } if(wcz=='-') { wcz=getchar(); czydz=1; } while(wcz>=48&&wcz<=57) { ret=ret*10+wcz-48; wcz=getchar(); } if(czydz) return -ret; return ret; } int main() { a=szybwczyt(); mantra[0].push_back(pom); vector<pair<int,int>>test; for(int i=0;i<a;++i) { t=szybwczyt(); if(t==0) { ++mal; --i; --a; } else if(t<0) { najw=mantra[i][0].second; pom.second=mantra[i][0].second+t; pom.first=mantra[i][0].first+mal; mantra[i+1].push_back(pom); if(mantra[i][0].second>=0) { pom.second=t; pom.first=mantra[i][0].first; mantra[i+1].push_back(pom); } for(int j=1;j<mantra[i].size();++j) { if(mantra[i][j].second>najw) { najw=mantra[i][j].second; pom.second=mantra[i][j].second+t; pom.first=mantra[i][j].first+mal; mantra[i+1].push_back(pom); if(mantra[i][j].second>=0) { pom.second=t; pom.first=mantra[i][j].first; mantra[i+1].push_back(pom); } } } mal=1; sort(mantra[i+1].begin(),mantra[i+1].end(),comp); } else { l=mantra[i].size(); najw=mantra[i][0].second; pom.second=mantra[i][0].second+t; pom.first=mantra[i][0].first+mal; mantra[i+1].push_back(pom); if(mantra[i][0].second>=0) { pom.second=t; pom.first=mantra[i][0].first; mantra[i+1].push_back(pom); } for(int j=1;j<l;++j) { if(mantra[i][j].second>najw) { najw=mantra[i][j].second; if(mantra[i][j].second>=0) { pom.second=t; pom.first=mantra[i][j].first; mantra[i+1].push_back(pom); } pom.second=mantra[i][j].second+t; pom.first=mantra[i][j].first+mal; mantra[i+1].push_back(pom); } } sort(mantra[i+1].begin(),mantra[i+1].end(),comp); mal=1; } } for(int i=0;i<mantra[a].size();++i) { if(mantra[a][i].second>=0) { printf("%d",mantra[a][i].first); return 0; } } printf("-1"); return 0; } |