oj.uz

Submission #409492

# Submission time Handle Problem Language Result Execution time Memory
409492 2021-05-20T23:36:19 Z ScarletS Toll (BOI17_toll) C++17
0 / 100
 136 ms 158380 KB 
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
int dp[100001][5][16][5];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int k,n,m,o,x,y,z,a,b;
    cin>>k>>n>>m>>o;
    memset(dp,INF,sizeof dp);
    // for (int g=0;g<100001;++g)
    //     for (int h=0;h<5;++h)
    //         for (int i=0;i<16;++i)
    //             for (int j=0;j<5;++j)
    //                 dp[g][h][i][j]=INF;
    while (m--)
    {
        cin>>x>>y>>z;
        dp[x/k][x%k][0][y%k]=z;
    }
    for (int i=1;i<16;++i)
        for (int g=0;g<=n/k;++g)
            for (int h=0;h<k;++h)
                for (int j=0;j<k;++j)
                    for (int f=0;f<k;++f)
                        dp[g][h][i][j]=min(dp[g][h][i][j],dp[g][h][i-1][f]+dp[g+(1<<(i-1))][f][i-1][j]);
    while (o--)
    {
        cin>>x>>y;
        a=x/k;
        b=y/k;
        vector<int> v(k,INF);
        v[x%k]=0;
        for (int h=15;h>=0;--h)
            if (a+(1<<h)<=b)
            {
                vector<int> w(k,INF);
                for (int i=0;i<k;++i)
                    for (int j=0;j<k;++j)
                        w[j]=min(w[j],v[i]+dp[a][i][h][j]);
                swap(v,w);
                a+=(1<<h);
            }
        if (v[y%k]==INF)
            v[y%k]=-1;
        cout<<v[y%k]<<"\n";
    }
    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 111 ms 157764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 136 ms 158380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 156828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 156828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 111 ms 157764 KB Output isn't correct
2 Halted 0 ms 0 KB -