Submission | WnSOJ

Submission #40

ID	Time	User	Problem	Language	Verdict	Time	Memory
40	Apr/14/2025 12:55	admin	The Enchanted Forest Trail	cpp	AC	27 ms	4352 KB

Source Code

Theme:

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

bool isPrime(long long n) {
    if(n < 2) return false;
    if(n == 2 || n == 3) return true;
    if(n % 2 == 0 || n % 3 == 0) return false;
    for(long long i = 5; i * i <= n; i += 6)
        if(n % i == 0 || n % (i + 2) == 0)
            return false;
    return true;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N; long long M;
    cin >> N >> M;
    vector<long long> stones(N);
    vector<int> primeFlag(N, 0);
    for(int i = 0; i < N; i++){
        cin >> stones[i];
        primeFlag[i] = isPrime(stones[i]);
    }
    
    long long currentSum = 0;
    int currentPrimeCount = 0, ans = -1, left = 0;
    for(int right = 0; right < N; right++){
        currentSum += stones[right];
        currentPrimeCount += primeFlag[right];
        while(currentSum > M && left <= right){
            currentSum -= stones[left];
            currentPrimeCount -= primeFlag[left];
            left++;
        }
        if(currentSum == M)
            ans = max(ans, currentPrimeCount);
    }
    
    cout << ans;
    return 0;
}