oj.uz

Submission #678753

# Submission time Handle Problem Language Result Execution time Memory
678753 2023-01-06T13:15:49 Z alexdd Toll (BOI17_toll) C++17
7 / 100
 1167 ms 393596 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<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 441 ms 392652 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 7380 KB Output is correct
7 Correct 5 ms 7380 KB Output is correct
8 Correct 452 ms 392636 KB Output is correct
9 Correct 426 ms 392484 KB Output is correct
10 Correct 229 ms 390980 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 392552 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 6 ms 7472 KB Output is correct
8 Correct 8 ms 7448 KB Output is correct
9 Correct 468 ms 392560 KB Output is correct
10 Incorrect 1167 ms 393596 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
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 412 ms 392512 KB Output is correct
11 Correct 586 ms 392528 KB Output is correct
12 Incorrect 767 ms 393456 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
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 412 ms 392512 KB Output is correct
11 Correct 586 ms 392528 KB Output is correct
12 Incorrect 767 ms 393456 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 441 ms 392652 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 7380 KB Output is correct
7 Correct 5 ms 7380 KB Output is correct
8 Correct 452 ms 392636 KB Output is correct
9 Correct 426 ms 392484 KB Output is correct
10 Correct 229 ms 390980 KB Output is correct
11 Correct 759 ms 392552 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 6 ms 7472 KB Output is correct
18 Correct 8 ms 7448 KB Output is correct
19 Correct 468 ms 392560 KB Output is correct
20 Incorrect 1167 ms 393596 KB Output isn't correct
21 Halted 0 ms 0 KB -