Any hints?

Hello all. I am doing task #1701, but ,actually, my question is also related to other equal tasks: how can you not exceed the time limit when the task supposes large array as the answer? For instance, in mentioned task the time is limited to 2 seconds. In case when N == 50 000, if possible set of emplyee's salaries exists, you need write 50 000 strings to console. But, as i have found out by measurig, only outputting array to the console takes over 3-5 seconds. Test it using C# and C++ with array of int values set to "0".

Edited by author 05.03.2018 09:04

If you use set<A*> or std::sort/std::stable_sort vector/array of pointers, your comparator won't work, because you need special comparator, like this

struct APtrCmp
{
  bool operator()(const A* lhs, const A* rhs) const  { /* implement logic here */ }
};
set<A*, APtrCmp> yourSet;

Good luck! ;)

#include <stdio.h>
#include <math.h>

int plus(int number){
    return number*(number+1)/2;
}
int minus(int number){
    return (-(number*(number+1)/2))+number;
}
int main(){
    int N;

    scanf("%d",&N);
    if(abs(N)>=1  && abs(N)<=10000){

        if(N<0)
            printf("%d",minus(N));
        else
            printf("%d",plus(N));
    }


}

this task is the same as 1075, but with a different number of dimensions(it doesn't really matter)

3 different solutions gets WA24. Is this test correct or I don't understand the statement?

If we run GCC 7.1, we can as well use -std=gnu++17

Before sending your solution try this test on your pc and make sure
that pc can calculate it faster than 10 hours :))

10000
10000
10000
10000
10000
10000
10000
10000
10000
10000
1

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace РџРѕРІРѕСЂРѕС‚
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] mas = Console.ReadLine().Split(' ');
            int k = int.Parse(mas[0]);
            int n = int.Parse(mas[1]);
            int[] A = Console.ReadLine().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(i => int.Parse(i)).ToArray();
            int M = 0;
            for (int i = 0; i < n; i++)
            {
                M += A[i];
                if (M - k >= 0)
                {M -= k;}
                else
                {M = 0;}
            }
            Console.WriteLine(M);
        }
    }
}
Надеюсь понятно всё.

Have solved this task in Python many years ago.
How test my code on Python and have Accept
This code on Ruby have WA on test №3

My program gets wa#3
test 3:
6
1 2 3 4 5 6
1 1
1 6
2 3
3 3
4 4
5 5
my program out:
Perfect!
1 3 4 5 6 2

it's wrong?

If you have program which gives right answer for the problem, but it's too slow and gets TLE, then you may just calculate answers for every possible input(there are only 81 possible variants of input, so you can calculate them all) and then create another program: put array of 81 possible answers in this program and them just read s from input and write in output corresponding answer from the array.
I had made such program and it got AC.

it may help:

            line = Console.ReadLine();
            while (line.Length < N)
            {
                line += Console.ReadLine();
            }

1 0
0 1
4 1
2 0

Answer: 0

Just like what I have said,I got a TLE and execution time is 1.029.
Who can help me?

I got TL#6.

After that just a little bit updated my solution:

int max( int pos, int len )
{
..if ( ch[pos][len] )
....return dp[pos][len];
---
....ch[pos][len] = 1;
....dp[pos][len] = res;
....return res;
---
}

and got AC in 0.015s.

Edited by author 23.03.2010 20:30

6 4
1 2 20
2 5 100
2 3 20
6 3 70
4 1 10

by the way : before you　use the dynamic programming on the tree structure, be sure you have build the tree correctly. That's why I got WA.

Source Code is available at :
ecnu_zp@yahoo.cn

explain me the way of doing it or give a solution

Edited by author 21.02.2018 16:21

What is the second test case?

Make sure your graph is more than 1296 and try these

3
2
1 2 0
1 5 0
*
3
1 8 2 3 0
1 -5 0
2 25 0
*
2
1 8 2 22 3 -15 0
2 19 3 -50 0

ans = -20

===========================

4
2
1 2 0
1 5 0
*
4
1 8 2 3 0
1 -5 0
2 25 0
1 22 2 -3 0
*
3
1 8 2 22 3 -15 0
2 19 3 -50 0
4 -1 2 -5 0
*
4
1 -8 2 18 0
1 -5 0
2 -19 3 -22 0
1 12 0

ans= -39

==============================

2
2
1 2 0
1 5 0
*
4
1 8 2 3 0
1 -5 0
2 25 0
1 22 2 -3 0

ans = -3

==========================

4
2
1 2 0
1 5 0
*
4
1 81 2 23 0
1 56 0
2 25 0
1 22 2 -31 0
*
3
1 8 2 22 3 -15 0
2 19 3 -50 0
4 -1 2 -5 0
*
4
1  82 2 18 0
1  59 0
2  39 3 52 0
1 112 0

ans = -2