Submission #228614

#	Time	Username	Problem	Language	Result	Execution time	Memory
228614		Ruxandra985	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	18 ms	1664 KiB

ho_t3

#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;

            //if (i == 12 && j == 1)
              //  printf ("a");

            /// 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++){
            if (i + j <= n)
                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 (stderr)

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: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75