oj.uz

Submission #1000852

# Submission time Handle Problem Language Result Execution time Memory
1000852 2024-06-18T10:19:07 Z Otalp Soccer (JOI17_soccer) C++14
100 / 100
 466 ms 67412 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back

int ddp[600][600];
int dp[600][600][3];
int a[600][600];


void solve(){
    int n, m;
    cin>>n>>m;
    int A, B, C;
    cin>>A>>B>>C;
    int k;
    cin>>k;
    vector<pii> q;
    multiset<pair<int, pii> > ds;
    for(int i=1; i<=k; i++){
        int l, r;
        cin>>l>>r;
        q.pb({l, r});
        ds.insert({1, {l, r}});
    }
    vector<pii> nap = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
    while(ds.size()){
        auto it = ds.begin();
        int x=it -> ss.ff, y = it -> ss.ss;
        if(ddp[x][y]){
            ds.erase(ds.begin());
            continue;
        }
        ddp[x][y] = it -> ff;
        ds.erase(it);
        for(pii h: nap){
            int l=x+h.ff, r=y+h.ss;
            if(l < 0 or l > n or r < 0 or r > m) continue;
            if(ddp[l][r]) continue;
            ds.insert({ddp[x][y] + 1, {l, r}});
        }
    }
    //for(int i=0; i<=n; i++){
    //    for(int j=0; j<=m; j++){
    //        cout<<ddp[i][j]<<' ';
    //    }
    //    cout<<'\n';
    //}
    multiset<pair<int, pair<pii, int>>> s;
    s.insert({1, {q[0], 0}});
    while(s.size()){
        auto it = s.begin();
        int x=it->ss.ff.ff, y=it->ss.ff.ss;
        int f=it->ss.ss;
        //cout<<x<<' '<<y<<' '<<f<<'\n';
        if(dp[x][y][f]){
            s.erase(it);
            continue;
        }
        dp[x][y][f] = it -> ff;
        s.erase(it);
        if(f == 1){
            if(!dp[x][y][0]) s.insert({dp[x][y][f], {{x, y}, 0}});
            for(int i=2; i<4; i++){
                int l=nap[i].ff + x, r=nap[i].ss + y;
                if(l < 0 or l > n or r < 0 or r > m) continue;
                if(dp[l][r][f]) continue;
                s.insert({dp[x][y][f] + A, {{l, r}, f}});
            }
        }
        if(f == 2){
            if(!dp[x][y][0]) s.insert({dp[x][y][f], {{x, y}, 0}});
            for(int i=0; i<2; i++){
                int l=nap[i].ff + x, r=nap[i].ss + y;
                if(l < 0 or l > n or r < 0 or r > m) continue;
                if(dp[l][r][f]) continue;
                s.insert({dp[x][y][f] + A, {{l, r}, f}});
            }
        }
        if(f == 0){
            if(!dp[x][y][1]) s.insert({dp[x][y][f] + (ddp[x][y] - 1) * C + B, {{x, y}, 1}});
            if(!dp[x][y][2]) s.insert({dp[x][y][f] + (ddp[x][y] - 1) * C + B, {{x, y}, 2}});
            for(int i=0; i<4; i++){
                int l=nap[i].ff + x, r=nap[i].ss + y;
                if(l < 0 or l > n or r < 0 or r > m) continue;
                if(dp[l][r][f]) continue;
                s.insert({dp[x][y][f] + C, {{l, r}, 0}}); 
            }
        }
    }
    int x=q[k-1].ff, y=q[k-1].ss;
    cout<<min(dp[x][y][0], min(dp[x][y][1], dp[x][y][2])) - 1<<'\n';
}


signed main(){
    solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 10580 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 275 ms 34896 KB Output is correct
4 Correct 317 ms 36432 KB Output is correct
5 Correct 86 ms 11348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 44140 KB Output is correct
2 Correct 307 ms 44624 KB Output is correct
3 Correct 224 ms 32340 KB Output is correct
4 Correct 267 ms 29780 KB Output is correct
5 Correct 218 ms 33876 KB Output is correct
6 Correct 241 ms 31172 KB Output is correct
7 Correct 348 ms 67412 KB Output is correct
8 Correct 320 ms 48048 KB Output is correct
9 Correct 341 ms 48464 KB Output is correct
10 Correct 45 ms 11864 KB Output is correct
11 Correct 355 ms 58216 KB Output is correct
12 Correct 326 ms 44664 KB Output is correct
13 Correct 241 ms 25680 KB Output is correct
14 Correct 346 ms 61152 KB Output is correct
15 Correct 263 ms 46048 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 10580 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 275 ms 34896 KB Output is correct
4 Correct 317 ms 36432 KB Output is correct
5 Correct 86 ms 11348 KB Output is correct
6 Correct 316 ms 44140 KB Output is correct
7 Correct 307 ms 44624 KB Output is correct
8 Correct 224 ms 32340 KB Output is correct
9 Correct 267 ms 29780 KB Output is correct
10 Correct 218 ms 33876 KB Output is correct
11 Correct 241 ms 31172 KB Output is correct
12 Correct 348 ms 67412 KB Output is correct
13 Correct 320 ms 48048 KB Output is correct
14 Correct 341 ms 48464 KB Output is correct
15 Correct 45 ms 11864 KB Output is correct
16 Correct 355 ms 58216 KB Output is correct
17 Correct 326 ms 44664 KB Output is correct
18 Correct 241 ms 25680 KB Output is correct
19 Correct 346 ms 61152 KB Output is correct
20 Correct 263 ms 46048 KB Output is correct
21 Correct 90 ms 7860 KB Output is correct
22 Correct 384 ms 27396 KB Output is correct
23 Correct 337 ms 24168 KB Output is correct
24 Correct 349 ms 23636 KB Output is correct
25 Correct 307 ms 25684 KB Output is correct
26 Correct 323 ms 23632 KB Output is correct
27 Correct 290 ms 26044 KB Output is correct
28 Correct 301 ms 29292 KB Output is correct
29 Correct 326 ms 19720 KB Output is correct
30 Correct 298 ms 24764 KB Output is correct
31 Correct 387 ms 58628 KB Output is correct
32 Correct 466 ms 38588 KB Output is correct
33 Correct 231 ms 31568 KB Output is correct
34 Correct 440 ms 33652 KB Output is correct
35 Correct 351 ms 18368 KB Output is correct