oj.uz

Submission #1007584

# Submission time Handle Problem Language Result Execution time Memory
1007584 2024-06-25T08:11:35 Z dimashhh Soccer (JOI17_soccer) C++17
35 / 100
 3000 ms 21088 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
const int  N = 5e2 + 2, MOD = (int)1e9 + 7;
const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
int n,m,d[N][N];
ll val[N][N];
ll a,b,c;
queue<pair<int,int>> q;
bool check(int x,int y){
    return (x >= 1 && x <= n && y >= 1 && y <= m);
}
set<pair<ll,pair<int,int>>> st;
int fx,fy;
ll dist[N][N];
bool vis[N][N];
void test(){
    cin >> n >> m >> a >> b >> c;
    n++;
    m++;
    int f;cin >> f;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            d[i][j] = 1e9;
            dist[i][j] = 1e17;
        }
    }
    for(int i = 1;i <= f;i++) {
        int s,t;
        cin >> s >> t;
        s++;
        t++;
        if(i == 1){
            vis[s][t] = 1;
            dist[s][t] = 0;
            st.insert({0,{s,t}});
        }
        d[s][t] = 0;
        q.push({s,t});
        fx = s;fy = t;
    }
    while(!q.empty()){
        auto [x,y] = q.front();q.pop();
        val[x][y] = d[x][y] * c;
        for(int i = 0;i < 4;i++){
            int x1 = x + dx[i],y1 = y + dy[i];
            if(check(x1,y1) && d[x1][y1] > d[x][y] + 1){
                d[x1][y1] = d[x][y] +1;
                q.push({x1,y1});
            }
        }
    }
    while(!st.empty()){
        auto [d,t] = (*st.begin());
        st.erase(st.begin());
        int x = t.first,y = t.second;vis[x][y] = 1;
        for(int x1 = x + 1;x1 <= n;x1++) {
            if(vis[x1][y]) break;
            ll dd = min(abs(x - x1) * 1ll * c + dist[x][y],
                        dist[x][y] + val[x1][y] + abs(x1 - x) * a + (x1 != x ? b : 0));
            if (dd < dist[x1][y]) {
                st.erase({dist[x1][y], {x1, y}});
                dist[x1][y] = dd;
                st.insert({dist[x1][y], {x1, y}});
            }
        }
        for(int x1 = x - 1;x1 >= 1;x1--) {
            if(vis[x1][y]) break;
            ll dd = min(abs(x - x1) * 1ll * c + dist[x][y],
                        dist[x][y] + val[x1][y] + abs(x1 - x) * a + (x1 != x ? b : 0));
            if (dd < dist[x1][y]) {
                st.erase({dist[x1][y], {x1, y}});
                dist[x1][y] = dd;
                st.insert({dist[x1][y], {x1, y}});
            }
        }
        for(int y1 = 1;y1 <= m;y1++) {
            ll dd = min(abs(y - y1) * 1ll * c + dist[x][y],
                        dist[x][y] + val[x][y1] + abs(y - y1) * a + (y1 != y ? b : 0));
            if (dd < dist[x][y1]) {

                st.erase({dist[x][y1], {x, y1}});
                dist[x][y1] = dd;
                st.insert({dist[x][y1], {x, y1}});
            }
        }
    }
    cout << dist[fx][fy];
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1;
    // cin >> t;
    while(t--){
        test();
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 7516 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 392 ms 14928 KB Output is correct
4 Correct 828 ms 15816 KB Output is correct
5 Correct 94 ms 9052 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 19028 KB Output is correct
2 Correct 442 ms 19796 KB Output is correct
3 Correct 358 ms 15200 KB Output is correct
4 Correct 322 ms 13908 KB Output is correct
5 Correct 350 ms 15536 KB Output is correct
6 Correct 392 ms 17812 KB Output is correct
7 Correct 418 ms 21088 KB Output is correct
8 Correct 490 ms 21004 KB Output is correct
9 Correct 417 ms 20820 KB Output is correct
10 Correct 28 ms 7768 KB Output is correct
11 Correct 452 ms 21028 KB Output is correct
12 Correct 457 ms 20304 KB Output is correct
13 Correct 281 ms 15920 KB Output is correct
14 Correct 396 ms 20820 KB Output is correct
15 Correct 286 ms 17908 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 7516 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 392 ms 14928 KB Output is correct
4 Correct 828 ms 15816 KB Output is correct
5 Correct 94 ms 9052 KB Output is correct
6 Correct 455 ms 19028 KB Output is correct
7 Correct 442 ms 19796 KB Output is correct
8 Correct 358 ms 15200 KB Output is correct
9 Correct 322 ms 13908 KB Output is correct
10 Correct 350 ms 15536 KB Output is correct
11 Correct 392 ms 17812 KB Output is correct
12 Correct 418 ms 21088 KB Output is correct
13 Correct 490 ms 21004 KB Output is correct
14 Correct 417 ms 20820 KB Output is correct
15 Correct 28 ms 7768 KB Output is correct
16 Correct 452 ms 21028 KB Output is correct
17 Correct 457 ms 20304 KB Output is correct
18 Correct 281 ms 15920 KB Output is correct
19 Correct 396 ms 20820 KB Output is correct
20 Correct 286 ms 17908 KB Output is correct
21 Correct 89 ms 8620 KB Output is correct
22 Correct 780 ms 15952 KB Output is correct
23 Correct 744 ms 16820 KB Output is correct
24 Correct 636 ms 18260 KB Output is correct
25 Correct 491 ms 17684 KB Output is correct
26 Correct 799 ms 16208 KB Output is correct
27 Correct 377 ms 15836 KB Output is correct
28 Correct 628 ms 16580 KB Output is correct
29 Correct 2599 ms 15940 KB Output is correct
30 Execution timed out 3030 ms 17188 KB Time limit exceeded
31 Halted 0 ms 0 KB -