Submission #1139329

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139329		Aliyyiakbar	Race (IOI11_race)	C++20	9 / 100	2426 ms	1860 KiB

race

#include "race.h"
#include "bits/stdc++.h"
using namespace std;

int best_path(int n, int k, int h[][2], int l[])
{
    /*
    vector<vector< pair<int, int> >> v(n + 1, vector< pair<int, int> >(0));
    for (int i = 0; i < n; ++i)
    {
        v[h[i][0]].push_back({h[i][1], l[i]});
        v[h[i][1]].push_back({h[i][0], l[i]});
    }
    */
    vector<int> dp(n + 5);
    --n;
    for (int i = 1; i <= n; ++i)
    {
        dp[i] = (dp[i - 1] + l[i - 1]);
    }
    int res = 1e9;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = i; j <= n; ++j)
        {
            if (dp[j] - dp[i - 1] == k)
            {
                res = min(res, j - i + 1);
                break;
            }
        }
    }
    if (res == 1e9)
    {
        return -1;
    }
    return res;
}

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