Submission #910021

#	Time	Username	Problem	Language	Result	Execution time	Memory
910021		vjudge1	Race (IOI11_race)	C++17	9 / 100	22 ms	6740 KiB

race

#include <bits/stdc++.h>

//Debug
#define DEBUG_ON false
#define DBG(x) if(DEBUG_ON) cout << "Line(" << __LINE__ << ") -> " << #x << " = " << (x) << "\n";

//Macros
#define rep(i, n) for(int i=0; i<n; i++)
#define pii pair<int, int>

typedef long long ll;

using namespace std;

//==================================
//GLOBALS
vector<ll> prefix;

//==================================

ll range_query(int l, int r){
    if(l > 0)
        return prefix[r]-prefix[l-1];
    return prefix[r];
}

bool possible(int n, ll target, int sz){
    int start=0, end=sz-1;
    ll aux;

    while(start < n && end < n){
        aux = range_query(start, end);
        //check
        if(aux == target) return true;

        //slide
        aux -= range_query(start, start);
        start++;
        end++;
    }
    return false;
}


int best_path(int N, int K, int H[][2], int L[]){
    //Prefixes
    prefix.assign(N-1, 0);
    rep(i, N-1){
        prefix[i] = L[i];
        if(i > 0)
            prefix[i] += prefix[i-1];
    }

    //Solve
    for(int sz=1; sz<=N-1; sz++)
        if(possible(N-1, K, sz)) return sz;
    
    return -1;
}


//==================================

• Subtask 1: 9 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57