oj.uz

Submission #228613

# Submission time Handle Problem Language Result Execution time Memory
228613 2020-05-02T06:58:05 Z Ruxandra985 Collecting Stamps 3 (JOI20_ho_t3) C++14
0 / 100
 5 ms 384 KB 
#include <bits/stdc++.h>
#define DIMN 210
#define INF 2000000000
using namespace std;
long long v[DIMN] , t[DIMN];
pair <long long , long long> dp[2][DIMN][DIMN];
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    long long n , l , i , j , curr , poz , timp , urm , sol = 0 , went , j2;
    fscanf (fin,"%lld%lld",&n,&l);

    for (i = 1 ; i <= n ; i++)
        fscanf (fin,"%lld",&v[i]);

    v[n + 1] = l;

    for (i = 1 ; i <= n ; i++)
        fscanf (fin,"%lld",&t[i]);

    for (i = 0 ; i <= n + 1 ; i++){
        for (j = 0 ; j <= n + 1 ; j++){
            dp[0][i][j] = dp[1][i][j] = make_pair(INF , 0);
        }
    }

    dp[1][0][0] = dp[0][0][0] = make_pair(0 , 0);

    for (went = 0 ; went <= n ; went++){

        for (i = 0 ; i <= n && i <= went ; i++){

            j2 = n - (went - i) + 1;
            j = went - i;

            /// se presupune ca dp[0/1][i][j] sunt calculate

            /// pt cazul cu 0


            timp = dp[0][i][j].first;
            curr = dp[0][i][j].second;
            /// vreau sa revin in j

            timp = timp + v[i] + l - v[j2];
            poz = v[j2];
            /// sunt inapoi in j, acum o sa ma duc mai departe prin j


            urm = j2;

            while (poz != v[i]){
                timp += poz - v[urm - 1];

                if (t[urm - 1] >= timp)
                    curr++;

                poz = v[urm - 1];
                urm--;

                /// te ai mutat altundeva

                if (dp[1][i][n - urm + 1].second < curr || (dp[1][i][n - urm + 1].first > timp && dp[1][i][n - urm + 1].second == curr)){
                    dp[1][i][n - urm + 1] = make_pair(timp , curr);

                    //if (i == 2 && n - urm + 1 == 4){
                      //  printf ("%lld\n", curr);
                    //}
                }

            }


            /// ----------------------------------------------------------------------


            /// pt cazul cu 1

            timp = dp[1][i][j].first;
            curr = dp[1][i][j].second;
            /// vreau sa revin in i

            timp = timp + v[i] + l - v[j2];
            /// sunt inapoi in i, acum o sa ma duc mai departe prin i


            urm = i;
            poz = v[i];

            while (poz != v[j2]){
                timp += v[urm + 1] - poz;

                if (t[urm + 1] >= timp)
                    curr++;

                poz = v[urm + 1];
                urm++;

                /// te ai mutat altundeva

                if (dp[0][urm][j].second < curr || (dp[0][urm][j].first > timp && dp[0][urm][j].second == curr)){
                    dp[0][urm][j] = make_pair(timp , curr);
                    //if (urm == 2 && j == 7){
                      //  printf ("%lld\n", curr);
                    //}
                }

            }



        }

    }


    for (i = 0 ; i <= n + 1 ; i++){
        for (j = 0 ; j <= n + 1 ; j++){
            sol = max(sol , max(dp[0][i][j].second , dp[1][i][j].second));
            //printf ("0 %lld %lld %lld\n" , i , j , dp[0][i][j].second);
            //printf ("1 %lld %lld %lld\n" , i , j , dp[1][i][j].second);
        }
    }


    fprintf (fout,"%lld",sol);

    return 0;
}

Compilation message

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:12:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%lld%lld",&n,&l);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
ho_t3.cpp:15:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%lld",&v[i]);
         ~~~~~~~^~~~~~~~~~~~~~~~~~
ho_t3.cpp:20:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%lld",&t[i]);
         ~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Incorrect 5 ms 384 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Incorrect 5 ms 384 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Incorrect 5 ms 384 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Incorrect 5 ms 384 KB Output isn't correct
17 Halted 0 ms 0 KB -