oj.uz

Submission #678750

# Submission time Handle Problem Language Result Execution time Memory
678750 2023-01-06T13:14:33 Z alexdd Toll (BOI17_toll) C++17
46 / 100
 3000 ms 396248 KB 
#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
const int dim = 2000;
const int INF = 1000000007;
int n,q,k,m;
vector<pair<int,int>> con[50001];
int dist[50001][dim];
int query(int st, int dr)
{
    if(dr<st)
        return INF;
    if(dr-st<dim)
        return dist[dr][(dr-st)];
    int mij=(st+dr)/2;
    int mnm=INF;
    for(int i=0;i<2*k+1;i++)
        mnm=min(mnm,query(st,mij+i)+query(mij+i,dr));
    return mnm;
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin>>k>>n>>m>>q;
    int a,b,c;
    for(int i=0;i<m;i++)
    {
        cin>>a>>b>>c;
        con[b].push_back({a,c});
    }
    for(int i=0;i<n;i++)
    {
        ///calc dist[i][]
        dist[i][0]=0;
        for(int j=1;j<=min(i,dim-1);j++)
        {
            dist[i][j] = INF;
            for(auto adj:con[i])
                if(adj.first >= i-j)
                    dist[i][j]=min(dist[i][j], dist[adj.first][(adj.first - i + j)] + adj.second);
        }
    }
    int rez;
    for(int i=0;i<q;i++)
    {
        cin>>a>>b;
        rez=query(a,b);
        if(rez>=INF)
            rez=-1;
        cout<<rez<<"\n";
    }
    return 0;
}
/**



*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 392568 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Correct 5 ms 7404 KB Output is correct
7 Correct 6 ms 7508 KB Output is correct
8 Correct 483 ms 393528 KB Output is correct
9 Correct 470 ms 393352 KB Output is correct
10 Correct 269 ms 391004 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1631 ms 392628 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 8 ms 7528 KB Output is correct
8 Correct 8 ms 7508 KB Output is correct
9 Correct 550 ms 393444 KB Output is correct
10 Execution timed out 3104 ms 395832 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 5 ms 7380 KB Output is correct
7 Correct 6 ms 7380 KB Output is correct
8 Correct 9 ms 7508 KB Output is correct
9 Correct 8 ms 7380 KB Output is correct
10 Correct 422 ms 393300 KB Output is correct
11 Correct 600 ms 394372 KB Output is correct
12 Correct 761 ms 395744 KB Output is correct
13 Correct 830 ms 396176 KB Output is correct
14 Correct 683 ms 394892 KB Output is correct
15 Correct 462 ms 236876 KB Output is correct
16 Correct 429 ms 237004 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 5 ms 7380 KB Output is correct
7 Correct 6 ms 7380 KB Output is correct
8 Correct 9 ms 7508 KB Output is correct
9 Correct 8 ms 7380 KB Output is correct
10 Correct 422 ms 393300 KB Output is correct
11 Correct 600 ms 394372 KB Output is correct
12 Correct 761 ms 395744 KB Output is correct
13 Correct 830 ms 396176 KB Output is correct
14 Correct 683 ms 394892 KB Output is correct
15 Correct 462 ms 236876 KB Output is correct
16 Correct 429 ms 237004 KB Output is correct
17 Correct 722 ms 394348 KB Output is correct
18 Correct 2 ms 1492 KB Output is correct
19 Correct 1 ms 1492 KB Output is correct
20 Correct 1 ms 1492 KB Output is correct
21 Correct 1 ms 1492 KB Output is correct
22 Correct 1 ms 1492 KB Output is correct
23 Correct 6 ms 7508 KB Output is correct
24 Correct 7 ms 7508 KB Output is correct
25 Correct 9 ms 7528 KB Output is correct
26 Correct 8 ms 7508 KB Output is correct
27 Correct 432 ms 393316 KB Output is correct
28 Correct 1432 ms 395928 KB Output is correct
29 Correct 1490 ms 396248 KB Output is correct
30 Correct 1340 ms 395036 KB Output is correct

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 392568 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Correct 5 ms 7404 KB Output is correct
7 Correct 6 ms 7508 KB Output is correct
8 Correct 483 ms 393528 KB Output is correct
9 Correct 470 ms 393352 KB Output is correct
10 Correct 269 ms 391004 KB Output is correct
11 Correct 1631 ms 392628 KB Output is correct
12 Correct 1 ms 1492 KB Output is correct
13 Correct 1 ms 1492 KB Output is correct
14 Correct 1 ms 1492 KB Output is correct
15 Correct 1 ms 1492 KB Output is correct
16 Correct 1 ms 1492 KB Output is correct
17 Correct 8 ms 7528 KB Output is correct
18 Correct 8 ms 7508 KB Output is correct
19 Correct 550 ms 393444 KB Output is correct
20 Execution timed out 3104 ms 395832 KB Time limit exceeded
21 Halted 0 ms 0 KB -