Rezultati

Up. imeNalogaJezikRezultatČas oddaje
finalsolution-2018 Gusarji C++ 100/100OK 13. okt '18 @ 15:10

Test Točke Porabljen spomin Porabljen čas Status
#1 4/4 12,570 MiB 0,004 s OK
#2 4/4 12,574 MiB 0,028 s OK
#3 4/4 12,574 MiB 0,004 s OK
#4 4/4 12,578 MiB 0,010 s OK
#5 4/4 12,582 MiB 0,022 s OK
#6 4/4 12,582 MiB 0,016 s OK
#7 4/4 12,621 MiB 0,016 s OK
#8 4/4 12,789 MiB 0,022 s OK
#9 4/4 12,891 MiB 0,065 s OK
#10 4/4 12,902 MiB 0,059 s OK
#11 4/4 13,359 MiB 0,101 s OK
#12 4/4 13,648 MiB 0,156 s OK
#13 4/4 13,402 MiB 0,132 s OK
#14 4/4 13,035 MiB 0,107 s OK
#15 4/4 20,980 MiB 1,197 s OK
#16 4/4 21,551 MiB 0,819 s OK
#17 4/4 12,660 MiB 0,016 s OK
#18 4/4 12,660 MiB 0,010 s OK
#19 4/4 12,660 MiB 0,016 s OK
#20 4/4 12,578 MiB 0,016 s OK
#21 5/5 12,652 MiB 0,010 s OK
#22 5/5 12,660 MiB 0,028 s OK
#23 5/5 12,574 MiB 0,016 s OK
#24 5/5 12,660 MiB 0,022 s OK

Ocenjevani program (Gusarji.cpp):
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define INF (1LL << 55)
#define EPS 1e-3
#define maxn 555

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

vector<vector<ld> > v;

ld dp[maxn][maxn][2];
priority_queue<pair<ld, vector<int>>> pq;

ld raz(ld a, ld b, ld w){
    ld ret = (b - a + 360.0);
    if(ret > 360.0)
        ret -= 360.0;
    
    return ret  / (w * 360);
}

int main(){
    ld a, w;
    int n;
    cin >> a >> w >> n;
    for(int i = 0; i < n; i++){
        ld b, d, v1;
        cin >> b >> d >> v1;
        d -= 1.0;
        v1 /= 60.0;
        v.pb({b, d, v1});
    }
    
    v.pb({a, 1.0, 1.0});
    n++;
    
    sort(v.begin(), v.end());
    
    for(int i = 0; i < maxn; i++){
        for(int j =0 ; j < maxn; j++)
            dp[i][j][0] = dp[i][j][1] = INF;
    }
    
    int zac = lower_bound(v.begin(), v.end(), (vector<ld>) {a, 1.0, 1.0}) - v.begin();
    dp[zac][zac][0] = 0.0;
    pq.push(mp(-0, (vector<int>){zac, zac, 0}));
    
    while(!pq.empty()){
        ld dist = -pq.top().fi;
        int x = pq.top().se[0];
        int y = pq.top().se[1];
        int smer = pq.top().se[2];
        pq.pop();
        
      //  cout << dist << "  " << x << "  " << y << "  " << smer << "  " << dp[x][y][smer] <<  endl; 
        
        if(dist  > dp[x][y][smer] + EPS)
          continue;
        
        ld cur = v[x][0];
        if(smer == 1)
            cur = v[y][0];
    
        
        int nxt = (y + 1) % n;
        ld ntime = dist + raz(cur, v[nxt][0], w);
        ld maxtime = v[nxt][1] / v[nxt][2];
        
     //   cout << ntime << "  " << dp[x][nxt][1] << " " << maxtime << endl;
        if(ntime < dp[x][nxt][1] && ntime <= maxtime){ // && nxt != x){
            dp[x][nxt][1] = ntime;
            pq.push(mp(-ntime, (vector<int>) {x, nxt, 1}));
        }
        
        nxt = (x - 1+ n) % n;
        ntime = dist + raz(v[nxt][0], cur, w);
        maxtime = v[nxt][1] / v[nxt][2];
        if(ntime < dp[nxt][y][0] && ntime <= maxtime){// && nxt != y){
            dp[nxt][y][0] = ntime;
            pq.push(mp(-ntime,(vector<int>) {nxt, y, 0}));
        }
    }
    
    ld ans = INF;
    for(int i = 0; i < n; i++){
        int c = (i + 1) % n;    
        ans = min(ans, min(dp[c][i][0], dp[c][i][1]));        
    }
    if(ans > INF / 2.0){
        cout << "-1" << endl;
        return 0;
    }
    
    cout << fixed << setprecision(15) << ans << endl;
    
	return 0;
}