I think it is a hard problem,harder than some rating>1e4 problems...

I had WA7 when I computed maximal rotation angle incorrectly.

仇嘉明强

There are n subway stations on a subway line, numbered from 1 to n. The distance between the ith station and the i+1th station is s_i, which means the train need s_i minutes to drive from the ith station to the i+1th.
There are trains driving from 1 to n and trains driving from station n to station 1. The trains driving from station 1 to station n departs every d minutes at station 1 and the first one of that departs at d1 minutes. Similarly, The trains driving from station n to station 1 departs every d minutes too at station n and the first one of that departs at dn minutes. However, in this problem the trains are considered not to stay at any station, just drive past
A vistor is going to visit every station. He starts from station t. To visit a station, he has to take a train and get off at that station. It takes him 1 minutes to visit a staion, so that he cannot take the train he get off just now. The station t is considered visited. After all visits he need to return to station t.
You are going to make a plan for him so that the time cost is minimized. The time cost is calculated as (the time he has visited all stations and gets off a train to station t - the time he departs--getting on a train at station t (can be any train)). Output such time in minutes.
Input
n
s_1 s_2 ... s_(n-1)
t
d d1 dn

Edited by author 24.01.2024 09:02

Explanation of the sample:
One possible solution.
Take the train to n at 5 and get of to station 3 at 12.
Then take the train to 1 at 13 and get of to station 1 at 25.
Then take the train to n at 28 and get of to station 2 at 33.
It costs 33-5=28

Edited by author 24.01.2024 09:05

thx.

Да очень круто: https://forum.tatysite.net/showthread.php?t=13334 .

I got time exceeded error. Can somebody tell what is test case? Or tell me how can I optimize my code? I even found to solutions using dp.

void lemontale(int n,int k,vector<vector<BigInt>> &mem){
    BigInt big_n = BigInt(n);
    BigInt big_k = BigInt(k);
    BigInt dva_big = BigInt(2ull);
    if (mem[n-1][k] == BigInt()){
        if (n<0)
            return ;
        else if (k==0 && n==1){
            mem[n-1][k] = BigInt(1);

            }
        else if (k==0){
            lemontale(n-1,k_start,mem);
            mem[n-1][k] = mem[n-2][k_start];

            }
        else if (n<=k){
            BigInt rez = dva_big^big_n;

            mem[n-1][k] = rez;
            }
        else{

                lemontale(n-1,k_start,mem);
                lemontale(n-1,k-1,mem);
                mem[n-1][k] = mem[n-2][k-1]+mem[n-2][k_start];
            }
    }

}
void lemontale2(int n,int k,BigInt* mem){
    BigInt dva_big = BigInt(2ull);

    if (mem[n-1]==BigInt()){
        if (n<=k)
            mem[n-1] = dva_big^BigInt(n);
        else
            for(int i=0;i<=k;i++){
                if (n-i-1 != 0){
                    lemontale2(n-i-1,k,mem);
                    mem[n-1]+=mem[n-i-2];
                }
                else{
                    mem[n-1]+=1;
                }
            }
    }

}

Edited by author 10.01.2024 16:08

Edited by author 10.01.2024 16:09

Edited by author 10.01.2024 16:09

Edited by author 10.01.2024 16:09