Submission #857324

#	Time	Username	Problem	Language	Result	Execution time	Memory
857324		YassirSalama	Overtaking (IOI23_overtaking)	C++17	29 / 100	3567 ms	15960 KiB

overtaking

#include "overtaking.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <iomanip>
#include <cmath>
#include <limits>
#include <map>
#include <utility>
#include <cctype>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <functional>
#include <iterator>
using namespace std;
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define ll long long
#define mod 1000000007
#define all(v) v.begin(),v.end()
const int MAXN=1005,MAXM=1005;
ll dp[MAXN][MAXN];
ll t[MAXN];
ll w[MAXN];
ll x;
ll n,m;
ll l;
ll s[MAXM];
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{      
    l=L;
    n=N;
    for(int i=0;i<n;i++) t[i]=T[i],w[i]=W[i];
    x=X;
    m=M;
    for(int i=0;i<m;i++) s[i]=S[i];
    return;
}

long long arrival_time(long long Y)
{
    ll tt[n+1][m];
    ll ee[n+1][m];
    for(int i=0;i<=n;i++){
        for(int j=0;j<m;j++) tt[i][j]=0,
                             ee[i][j]=0;
    }
    for(int i=0;i<n;i++) tt[i][0]=t[i];
    tt[n][0]=Y;
    for(int i=1;i<m;i++){
        int ans=0;
        for(int j=0;j<n;j++){
            ee[j][i]=tt[j][i-1]+w[j]*(s[i]-s[i-1]);
        }
        ee[n][i]=tt[n][i-1]+x*(s[i]-s[i-1]);
        //nchufu f station i-1
        //haduk li jaw earlier
        for(int k=0;k<=n;k++){
            vector<int> v;
            for(int j=0;j<=n;j++){
                if(tt[j][i-1]<tt[k][i-1]) v.push_back(j);
            }
            ll a=0;
            a=max(a,ee[k][i]);
            for(auto x:v){
                a=max(a,ee[x][i]);
            }
            tt[k][i]=a;
        }
    }
    return tt[n][m-1];
}

#ifdef IOI
#include "overtaking.h"
#include <cassert>
#include <cstdio>
#include <vector>

int main()
{
    int L, N, X, M, Q;
    assert(5 == scanf("%d %d %d %d %d", &L, &N, &X, &M, &Q));
    std::vector<long long> T(N);
    for (int i = 0; i < N; i++)
        assert(1 == scanf("%lld", &T[i]));
    std::vector<int> W(N);
    for (int i = 0; i < N; i++)
        assert(1 == scanf("%d", &W[i]));
    std::vector<int> S(M);
    for (int i = 0; i < M; i++)
        assert(1 == scanf("%d", &S[i]));
    std::vector<long long> Y(Q);
    for (int i = 0; i < Q; i++)
        assert(1 == scanf("%lld", &Y[i]));

    fclose(stdin);

    init(L, N, T, W, X, M, S);
    std::vector<long long> res(Q);
    for (int i = 0; i < Q; i++)
        res[i] = arrival_time(Y[i]);

    for (int i = 0; i < Q; i++)
        printf("%lld\n", res[i]);
    fclose(stdout);
    return 0;
}
#endif

Compilation message (stderr)

overtaking.cpp: In function 'long long int arrival_time(long long int)':
overtaking.cpp:62:13: warning: unused variable 'ans' [-Wunused-variable]
   62 |         int ans=0;
      |             ^~~

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 0 / 10
• Subtask 3: 20 / 20
• Subtask 4: 0 / 26
• Subtask 5: 0 / 35