Submission #878312

#	Time	Username	Problem	Language	Result	Execution time	Memory
878312		Arshi	Toll (BOI17_toll)	C++17	56 / 100	3008 ms	5972 KiB

toll

/**********************GOD**********************/

#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <iterator>
#include <map>

using namespace std;

#pragma GCC Optimize("O3, Unroll-loops");

typedef long long ll;
typedef long double ld;
typedef pair<ll , ll> pll;

#define len                 length()
#define MP                  make_pair
#define fs                  first
#define sc                  second
#define pb                  push_back
#define all(x)              x.begin() , x.end()
#define kill(x)             cout << x , exit(0)

const int INF = 1e9 + 7;
const int MXN = 5e4 + 4;

int n, m, k;
int q;

vector<pair<int, int>> Q[MXN];
int adj[MXN][13];
int dist[MXN], ans[MXN];

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> k >> n >> m >> q;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < 13; j ++)
            adj[i][j] = INF;
    for(int i = 0; i < m; i ++) {
        int v, u, w; cin >> v >> u >> w;
        adj[u][u - v] = w;
    }
    for(int i = 0; i < q; i ++) {
        int v, u; cin >> v >> u;
        Q[v].pb({u, i});
    }

    for(int v = 0; v < n; v ++) {
        if(Q[v].empty())
            continue;
        for(int u = 0; u < n; u ++)
            dist[u] = INF;
        dist[v] = 0;
        for(int u = v + 1; u < n; u ++)
            for(int i = 1; i < 2 * k; i ++)
                if(u - i >= v)
                    dist[u] = min(dist[u], adj[u][i] + dist[u - i]);
                else
                    break;
        for(auto[u, i] : Q[v])
            ans[i] = (dist[u] < INF ? dist[u] : -1);
    }

    for(int i = 0; i < q; i ++)
        cout << ans[i] << '\n';

    return 0;
}

/*!
ahkh
*/

Compilation message (stderr)

toll.cpp:18: warning: ignoring '#pragma GCC Optimize' [-Wunknown-pragmas]
   18 | #pragma GCC Optimize("O3, Unroll-loops");
      |

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 0 / 44