oj.uz

Submission #847623

# Submission time Handle Problem Language Result Execution time Memory
847623 2023-09-10T05:24:38 Z adizbek Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 2 ms 5212 KB 
#include <bits/stdc++.h>
#define quan160607 "BoundSeq"
#define fi first
#define se second
#define pii pair<int, int>
#define piii pair<int, pii>
#define pb push_back
using namespace std;
typedef long long ll;
const ll oo = 1e18;
const int inf = 2e9;
const int nmax = 3e4 + 5;
void start()
{
//    freopen(quan160607".inp","r",stdin);
//    freopen(quan160607".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
 
int n, m;
int b[nmax], a[nmax], p[nmax];
vector<int> v[nmax];
const int block = 100;
int dp[nmax][block + 5];
priority_queue<piii, vector<piii>, greater<piii>> q;
 
bool minimize(int &a, int b)
{
    if(a > b)
    {
        a = b;
        return true;
    } else return false;
}
 
int ans = inf;
void solve_dij()
{
    for(int i = 0; i <= n; i++)
    {
        for(int j = 0; j <= block; j++)
            dp[i][j] = inf;
    }
    dp[b[0]][0] = 0;
    q.push({dp[b[0]][0], {b[0], 0}});
    while(!q.empty())
    {
        piii temp = q.top();
        q.pop();
        int u = temp.se.fi, pk = temp.se.se;
        if(u == b[1]) ans = min(ans, dp[u][pk]);
        if(temp.fi != dp[u][pk])
            continue;
        if(pk > 0)
        {
            if(u - pk >= 0) {
                if(minimize(dp[u - pk][pk], dp[u][pk] + 1))
                    q.push({dp[u - pk][pk], {u - pk, pk}});
                }
            if(u + pk < n) {
                if(minimize(dp[u + pk][pk], dp[u][pk] + 1))
                    q.push({dp[u + pk][pk], {u + pk, pk}});
            }
            if(dp[u][0] > dp[u][pk])
            {
                dp[u][0] = dp[u][pk];
                q.push({dp[u][0], {u, 0}});
            }
        }
        else if(pk == 0) {
            for(auto x : v[u])
            {
                if(x > block)
                {
                    int cnt = 0;
                    for(int i = u; i < n; i += x) {
                        if(minimize(dp[i][0], temp.fi + cnt)) {
                            q.push({dp[i][0], {i, 0}});
                        }
                        cnt++;
                    }
                    cnt = 0;
                    for(int i = u; i >= 0; i -= x) {
                        if(minimize(dp[i][0], temp.fi + cnt)) {
                            q.push({dp[i][0], {i, 0}});
                            cnt++;
                        }
                    }
                }
                else if(x <= block) {
                    if(minimize(dp[u][x], dp[u][pk]))
                        q.push({dp[u][x], {u, x}});
                }
            }
        }
    }
}
int main()
{
    start();
    cin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        cin >> b[i] >> p[i];
        v[b[i]].push_back(p[i]);
    }
    solve_dij();
    cout << (ans == inf ? -1 : ans);
//    cout << "\n";
//    cout << dp[2][0] << " " << dp[2][1];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 1 ms 2904 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 1 ms 2904 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 1 ms 2908 KB Output is correct
10 Correct 1 ms 2908 KB Output is correct
11 Correct 2 ms 3164 KB Output is correct
12 Correct 1 ms 2908 KB Output is correct
13 Correct 1 ms 2908 KB Output is correct
14 Correct 1 ms 3164 KB Output is correct
15 Correct 2 ms 3164 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 3160 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 1 ms 2908 KB Output is correct
10 Correct 1 ms 2908 KB Output is correct
11 Correct 2 ms 3164 KB Output is correct
12 Correct 1 ms 2908 KB Output is correct
13 Correct 1 ms 2908 KB Output is correct
14 Correct 1 ms 3164 KB Output is correct
15 Correct 1 ms 3164 KB Output is correct
16 Correct 1 ms 3164 KB Output is correct
17 Incorrect 2 ms 5212 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct
6 Correct 1 ms 2904 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 1 ms 2908 KB Output is correct
10 Correct 1 ms 2908 KB Output is correct
11 Correct 2 ms 3164 KB Output is correct
12 Correct 1 ms 2908 KB Output is correct
13 Correct 1 ms 2908 KB Output is correct
14 Correct 2 ms 3164 KB Output is correct
15 Correct 1 ms 3164 KB Output is correct
16 Correct 1 ms 2908 KB Output is correct
17 Incorrect 2 ms 5212 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 1 ms 2904 KB Output is correct
10 Correct 1 ms 2904 KB Output is correct
11 Correct 2 ms 3164 KB Output is correct
12 Correct 1 ms 2908 KB Output is correct
13 Correct 1 ms 2908 KB Output is correct
14 Correct 2 ms 3164 KB Output is correct
15 Correct 2 ms 3164 KB Output is correct
16 Correct 1 ms 3164 KB Output is correct
17 Incorrect 2 ms 5212 KB Output isn't correct
18 Halted 0 ms 0 KB -