제출 #1076954

#제출 시각아이디문제언어결과실행 시간메모리
1076954andrei_iorgulescuTortoise (CEOI21_tortoise)C++14
18 / 100
989 ms500 KiB
#include <bits/stdc++.h> #define all(x) (x).begin(),(x).end() using namespace std; //#ifndef DLOCAL // #define cin fin // #define cout fout // ifstream cin(".in"); // ofstream cout(".out"); //#endif using ll = long long; using ld = long double; #define int ll #define sz(x) ((int)(x).size()) using pii = pair<int,int>; using tii = tuple<int,int,int>; const int nmax = 5e5 + 5; int Ld[nmax], Rd[nmax]; int v[nmax]; bool possible(multiset<int> s) { int last = -1, timer = 0; for(auto x : s) { if(last == -1) { timer += x - 1; } else { if(Ld[last] != Ld[x] || Rd[last] != Rd[x]) timer += x - last; else timer += min(last - Ld[last] + x - Ld[last], Rd[last] - last + Rd[last] - x); } if(timer > 2 * (x - 1)) { return 0; } last = x; //cerr << timer << '\n'; } //cerr << '\n'; //for(auto x: s) cerr << x << ' '; cerr << '\n'; //cerr << "ok\n"; return 1; } signed main() { cin.tie(0) -> sync_with_stdio(0); int n; cin >> n; ll cost = 0; for(int i = 1; i <= n; i++) cin >> v[i], cost += (v[i] != -1? v[i] : 0); for(int lst = -1e9 - 5, i = 1; i <= n; i++) { if(v[i] == -1) lst = i; else Ld[i] = lst; } for(int lst = 1e9 + 5, i = n; i > 0; i--) { if(v[i] == -1) lst = i; else Rd[i] = lst; } vector<vector<int>> idxs(n + 1); multiset<int> sofar; for(int i = 1; i <= n; i++) { if(v[i] == -1) continue; idxs[min(Rd[i] - i, i - Ld[i])].emplace_back(i); } ll szm = 0; srand(time(NULL)); for(int i = 0; i < 1000; i++) { for (auto it : sofar) v[it]++; sofar.clear(); int itr = 0; vector<int> V; for(auto &T : idxs) { for (auto itt : T) V.push_back(itt); itr++; //sort(all(T), greater<int>()); if (itr % (1 + rand() % 5) == 0) { shuffle(V.begin(), V.end(), default_random_engine(rand())); for(auto x : V) { while(v[x] > 0) { sofar.emplace(x); if(possible(sofar)) v[x]--; else { sofar.erase(sofar.find(x)); break; } } } V.clear(); } } shuffle(V.begin(), V.end(), default_random_engine(rand())); for(auto x : V) { while(v[x] > 0) { sofar.emplace(x); if(possible(sofar)) v[x]--; else { sofar.erase(sofar.find(x)); break; } } } szm = max(szm, (ll)sofar.size()); } cout << cost - szm << '\n'; } /** Töte es durch genaue Untersuchung\Töte es kann es nur noch schlimmer machen\Es lässt es irgendwie atmen -- */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...