Submission #00355

ソースコード

?
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
//#define MYDEBUG
#include <bits/stdc++.h>
#ifdef MYDEBUG
#define dbp(x) cout<<#x<<": "<<x<<endl
#define dbp2(x,y) cout<<#x<<","<<#y<<": "<<x<<","<<y<<endl
#define dbp3(x,y,z) cout<<#x<<","<<#y<<","<<#z<<": "<<x<<","<<y<<","<<z<<endl
#define dbp4(w,x,y,z) cout<<#w<<","<<#x<<","<<#y<<","<<#z<<": "<<w<<","<<x<<","<<y<<","<<z<<endl
#define ifcin(x) std::ifstream cin(x)
#else
#define dbp(x)
#define dbp2(x,y)
#define dbp3(x,y,z)
#define dbp4(w,x,y,z)
#define ifcin(x)
#endif
#define ll long long
#define ull unsigned long long
#define all(x) x.begin(), x.end()
#define rep(i, from, to) for(int i=from; i<to; ++i)
#define REP(i, from, to) for(int i=from; i<=to; ++i)
#define EPS = 1e-14;
using std::vector;
using std::cout;
using std::cin;
using std::endl;
using std::max;
using std::min;
using std::swap;
using std::string;
using std::fill;
using std::pair;
using std::sort;
using std::reverse;
using std::pair;
using std::greater;
using std::priority_queue;
using std::ostream;
using std::unique;
using std::map;
template<typename T>
ostream& operator<<(ostream& out, const vector<vector<T> >& v) {
for (size_t i = 0; i < v.size(); ++i) {
out << v[i] << endl;
}
return out;
}
template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
out << "[";
size_t last = v.size() - 1;
for (size_t i = 0; i < v.size(); ++i) {
out << v[i];
if (i != last) {
out << ",";
}
}
out << "]";
return out;
}
static const ll MAX_N = 2 * 100010;
static const ll MIN_P = -10000000000000000;
typedef pair<ll, int> P;
ll n, p;
vector<ll> x, sum;
ll partial(ll L, ll R) { //(L, R]
if (L < 0) {
return MIN_P;
}
return sum[R] - sum[L];
}
void solve() {
cin >> n >> p;
x = vector<ll>(n + 1);
sum = vector<ll>(n + 1);
sum[0] = 0;
ll ans = 0;
REP(i,1,n)
{
cin >> x[i];
sum[i] = sum[i - 1] + x[i];
if (x[i] >= p) {
ans = 1;
}
}
REP(i,1,n)
{
sum[i] *= -1;
}
//よい(L, R]を見つける
//sum[L] <= sum[R] - p
//最も左側の(小さい)Lを探す
//sum[L]はsum[R]-p以下であること
//Lは最小であること
//最初のx以下を探す
//最初の-x以上を探す
std::set<P> st;
for (ll r = 1; r <= n; ++r) {
ll target = -sum[r] - p;
dbp3(r, sum[r], target);
target *= -1;
auto it = st.lower_bound(P(target, 0));
if (it != st.end()) {
P get = (*it);
dbp4(r, sum[r], get.first, get.second);
ll L = get.second;
if (-sum[r] - (-sum[L - 1]) < p) {
} else {
ans = max(ans, r - L + 1);
}
} else {
dbp4(r, sum[r], target, "no");
}
st.insert(P(sum[r], r));
}
cout << ans << endl;
}
int main() {
solve();
}

ステータス

項目 データ
問題 0001 - photography
ユーザー名 LitMc
投稿日時 2017-07-07 22:58:12
言語 C++11
状態 Wrong Answer
得点 0
ソースコード長 2730 Byte
最大実行時間 93 ms
最大メモリ使用量 14300 KB

セット

セット 得点 Cases
1 ALL 0 / 100 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
01_sample_01.in AC 11 ms 480 KB
1
01_sample_02.in AC 14 ms 452 KB
1
01_sample_03.in AC 15 ms 552 KB
1
01_sample_04.in AC 11 ms 528 KB
1
02_handmake_01.in AC 13 ms 624 KB
1
02_handmake_02.in AC 22 ms 596 KB
1
02_handmake_03.in AC 14 ms 448 KB
1
02_handmake_04.in AC 13 ms 552 KB
1
02_handmake_05.in AC 12 ms 524 KB
1
02_handmake_06.in AC 17 ms 496 KB
1
03_random_01.in WA 82 ms 12628 KB
1
03_random_02.in AC 79 ms 10528 KB
1
03_random_03.in AC 86 ms 11464 KB
1
03_random_04.in WA 67 ms 9636 KB
1
03_random_05.in WA 68 ms 9472 KB
1
03_random_06.in AC 72 ms 10644 KB
1
03_random_07.in WA 93 ms 14300 KB
1
03_random_08.in AC 60 ms 8892 KB
1
03_random_09.in WA 93 ms 13496 KB
1
03_random_10.in AC 75 ms 11540 KB
1