Submission #60749313

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
void solve() {
    int n,x;
    cin >> n >> x;
    int s = 0;
    vector<int> a(n+9),pre(n+9,0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s+=a[i];
        pre[i] = pre[i-1] + a[i];
    }
    x%=s;
    //cout << x << endl;
    if (x == 0) {
        cout << "Yes";
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;

#define ull unsigned long long
#define int long long
#define pii pair<int,int>

void solve() {
    int n,x;
    cin >> n >> x;
    int s = 0;
    vector<int> a(n+9),pre(n+9,0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s+=a[i];
        pre[i] = pre[i-1] + a[i];
    }
    x%=s;
    //cout << x << endl;
    if (x == 0) {
        cout << "Yes";
        return;
    }
    int t = 0;
    int j = 1;
    for (int i = 1; i <= n; i++) {
        t+=a[i];
        while (t > x) {
            t-=a[j];
            j = (j-1+1)%n+1;
        }
        if (t == x) {
            cout << "Yes";
            return;
        }
    }
    
    t = 0;
    j = n;
    for (int i = n; i >= 1; i--) {
        t+=a[i];
        while (t > x) {
            t-=a[j];
            j = (j-1-1)%n+1;
        }
        if (t == x) {
            cout << "Yes";
            return;
        }
    }

    t = x;
    for (int i = 1; i <= n; i++) {
        t-=a[i];
        if (t < 0) break;
        int l = 1;
        int r = n;
        while (l <= r) {
            int mid = (l+r)/2;
            if (pre[n]-pre[mid-1] == t) {
                cout << "Yes";
                return;
            }else if (pre[n] - pre[mid-1] < t) {
                r = mid-1;
            }else {
                l = mid+1;
            }
        }
    }

    t = x;
    for (int i = n; i >= 1; i--) {
        t-=a[i];
        if (t < 0) break;
        int l = 1;
        int r = n;
        while (l <= r) {
            int mid = (l+r)/2;
            if (pre[mid] == t) {
                cout << "Yes";
                return;
            }else if (pre[mid] > t) {
                r = mid-1;
            }else {
                l = mid+1;
            }
        }
    }

    cout << "No";
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    t = 1;
    for (int i = 0; i < t; i++) {
        solve();
    }
    return 0;
}

Submission Info

Judge Result