| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 234040 |
2020-05-22T21:47:47 Z |
DS007 |
Candies (JOI18_candies) |
C++14 |
|
9 ms |
1024 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
int solveTestCase(int test) {
int n;
cin >> n;
int a[n + 2] = {};
for (int i = 1; i <= n; i++) cin >> a[i];
int p1[n + 2] = {}, p2[n + 2] = {};
p1[1] = a[1];
for (int i = 2; i <= n; i++) {
if (i % 2)
p1[i] = a[i] + p1[i - 2];
else
p2[i] = a[i] + p2[i - 2];
}
set<pair<int, pair<int, int>>, decltype(greater<>())> s;
map<int, int> begin, end;
map<pair<int, int>, int> rev;
for (int i = 1; i <= n; i++) {
s.insert(make_pair(a[i], make_pair(i, i)));
begin[i] = i;
end[i] = i;
rev[{i, i}] = a[i];
}
ofstream cout("opt.txt");
int ans = 0;
for (int i = 1; i <= (n + 1) / 2; i++) {
if (i == 712)
cerr << "Here";
auto temp = s.begin();
ans += temp->first;
cout << ans << "\n";
pair<int, int> next = temp->second;
end.erase(next.second);
begin.erase(next.first);
rev.erase(next);
auto it1 = begin.find(next.second + 1);
if (it1 != begin.end()) {
next.second = it1->second - 1;
s.erase(make_pair(rev[*it1], *it1));
rev.erase(*it1);
end.erase(it1->second);
begin.erase(it1);
} else if(next.second == n)
cerr << i << "\n";
auto it2 = end.find(next.first - 1);
if (it2 != end.end()) {
next.first = it2->second + 1;
s.erase(make_pair(rev[{it2->second, it2->first}], make_pair(it2->second, it2->first)));
rev.erase({it2->second, it2->first});
begin.erase(it2->second);
end.erase(it2);
} else if(next.first == 1)
cerr << i << "\n";
int off = 0;
if (next.second == n)
next.second--, off += a[n];
else
next.second++;
if (next.first == 1)
next.first++, off += a[1];
else
next.first--;
s.erase(temp);
//assert((next.second - next.first) % 2 == 0 && next.second - next.first != 0);
int val = -off;
if (next.second == next.first)
val += a[next.second];
else
val += next.second % 2 ? p1[next.second] - p1[next.first] + a[next.first] - (p2[next.second - 1] - p2[next.first + 1] + a[next.first + 1]) : p2[next.second] - p2[next.first] + a[next.first] - (p1[next.second - 1] - p1[next.first + 1] + a[next.first + 1]);
s.insert(make_pair(val, next));
rev[next] = val;
begin.insert(next);
end[next.second] = next.first;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int test = 1;
//cin >> test;
for (int i = 1; i <= test; i++)
solveTestCase(i);
}
Compilation message
candies.cpp: In function 'long long int solveTestCase(long long int)':
candies.cpp:90:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
1024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
1024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
