Submission #349099
Source Code Expand
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
typedef long long ll;
template <int N>
struct FenwickTree {
ll seg[N];
void init() {
fill_n(seg, N, 0);
}
void add(int i, ll x) {
while (i < N) {
seg[i] += x;
i += (i+1) & ~i;
}
}
//[0, i)
ll sum(int i) {
ll s = 0;
int d = 1;
while (i >= d) {
i -= d;
s += seg[i];
d = (i+1) & ~i;
}
return s;
}
//[a, b)
ll sum(int a, int b) {
return sum(b) - sum(a);
}
};
const int MN = 100200;
FenwickTree<MN> fw;
//int d[MN];
ll mi[MN];
ll r;
int set(int i, int x) {
}
int sum() {
}
void input() {
int n;
ll *s = new ll[MN*2];
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%lld", s+i);
}
r = 0;
if (n % 2) {
s[n] = 1LL<<55;
r -= 1LL<<55;
n++;
}
r += s[0];
s[0] = 0;
fw.init();
for (int i = 0; i < n/2; i++) {
fw.add(i, s[i*2]);
}
mi[n/2] = 1LL<<55;
for (int i = n/2-1; i >= 0; i--) {
mi[i] = min(s[i*2], min(s[i*2+1], mi[i+1]));
}
for (int i = n/2-1; i >= 0; i--) {
r += max(s[i*2], min(s[i*2+1], mi[i+1]));
}
}
int main() {
input();
printf("%lld\n", r);
int q;
scanf("%d", &q);
assert(!q);
for (int i = 0; i < q; i++) {
int p; ll d;
scanf("%d %lld", &p, &d);
}
}
Submission Info
Submission Time |
|
Task |
D - コインの取り合い |
User |
yosupo |
Language |
C++11 (GCC 4.8.1) |
Score |
10 |
Code Size |
1638 Byte |
Status |
RE |
Exec Time |
353 ms |
Memory |
4272 KB |
Compile Error
./Main.cpp: In function ‘void input()’:
./Main.cpp:62:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
./Main.cpp:64:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", s+i);
^
./Main.cpp: In function ‘int main()’:
./Main.cpp:92:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
^
./Main.cpp:96:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %lld", &p, &d);
^
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Subtask3 |
Score / Max Score |
0 / 0 |
10 / 10 |
0 / 80 |
0 / 90 |
Status |
|
|
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt |
Subtask1 |
subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt |
Subtask2 |
sample_01.txt, sample_02.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt |
Subtask3 |
subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt, subtask3_08.txt, subtask3_09.txt, subtask3_10.txt, subtask3_11.txt, subtask3_12.txt, subtask3_13.txt, subtask3_14.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
RE |
281 ms |
1828 KB |
sample_02.txt |
RE |
280 ms |
1936 KB |
subtask1_01.txt |
AC |
29 ms |
1816 KB |
subtask1_02.txt |
AC |
80 ms |
4140 KB |
subtask1_03.txt |
AC |
68 ms |
3500 KB |
subtask1_04.txt |
AC |
83 ms |
4136 KB |
subtask1_05.txt |
AC |
82 ms |
4140 KB |
subtask1_06.txt |
AC |
64 ms |
4048 KB |
subtask1_07.txt |
AC |
81 ms |
4140 KB |
subtask2_01.txt |
RE |
288 ms |
1932 KB |
subtask2_02.txt |
RE |
300 ms |
2916 KB |
subtask2_03.txt |
RE |
333 ms |
4132 KB |
subtask2_04.txt |
RE |
329 ms |
4200 KB |
subtask2_05.txt |
RE |
325 ms |
4120 KB |
subtask2_06.txt |
RE |
318 ms |
4052 KB |
subtask2_07.txt |
RE |
320 ms |
4052 KB |
subtask2_08.txt |
AC |
105 ms |
4076 KB |
subtask2_09.txt |
RE |
353 ms |
2536 KB |
subtask2_10.txt |
RE |
323 ms |
4052 KB |
subtask2_11.txt |
RE |
314 ms |
4140 KB |
subtask2_12.txt |
RE |
316 ms |
4140 KB |
subtask3_01.txt |
RE |
298 ms |
2400 KB |
subtask3_02.txt |
RE |
339 ms |
4272 KB |
subtask3_03.txt |
RE |
333 ms |
4128 KB |
subtask3_04.txt |
RE |
344 ms |
4068 KB |
subtask3_05.txt |
AC |
63 ms |
4132 KB |
subtask3_06.txt |
RE |
345 ms |
4196 KB |
subtask3_07.txt |
RE |
330 ms |
4140 KB |
subtask3_08.txt |
RE |
344 ms |
4200 KB |
subtask3_09.txt |
RE |
337 ms |
4196 KB |
subtask3_10.txt |
RE |
323 ms |
4140 KB |
subtask3_11.txt |
RE |
310 ms |
3096 KB |
subtask3_12.txt |
RE |
334 ms |
4136 KB |
subtask3_13.txt |
RE |
339 ms |
4140 KB |
subtask3_14.txt |
RE |
340 ms |
4136 KB |