1121 - Subsequence

All about problems in Volume 11. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
holigan187
New poster
Posts: 3
Joined: Thu Aug 08, 2013 5:41 pm

1121 - Subsequence

Post by holigan187 »

Code: Select all

//Nguyen Duc Anh
//1121

#include<iostream>
#include<fstream>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<map>

#define fi "1121.inp"
#define fo "1121.out"

using namespace std;

long n;
long s[100005];
long goc;
int tong[100005];

void input()
{
	long i;
	
	for (i=1;i<=n;i++)
		scanf("%ld",&s[i]);
}

long tinh(int vt,int size)
{
	if ( size == 0 )
		tong[vt]=s[vt];
	else
		tong[vt]=tong[vt]+s[vt+size];
	
	return tong[vt];
}

void solve()
{
	long i,size;
	
	for (size=0;size<n;size++)
	{
		for (i=1;i<=n;i++)
		{
			if ( size + i > n )
				break;
			
			if ( tinh(i,size) >= goc )
			{
				printf("%ld\n",size+1);
				return;
			}
		}
	}
	
	printf("0\n");
}

int main()
{
	//freopen(fi,"r",stdin);
	//freopen(fo,"w",stdout);
	
	while (scanf("%ld %ld",&n,&goc) > 0 )
	{
		input();
		solve();
	}
	
	return 0;
}
i dont know why still WA , who can give me some critical in/out ? ty so much
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 1121 - WA

Post by brianfry713 »

That code gets TLE. Try solving it in O(N).
Check input and AC output for thousands of problems on uDebug!
Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

Re: 1121 - Subsequence

Post by Repon kumar Roy »

Use Sliding Window to get AC :)
Kazi_Tanvir_Ahsan
New poster
Posts: 1
Joined: Tue Oct 06, 2015 2:56 am

1121 - Subsequence

Post by Kazi_Tanvir_Ahsan »

I really need to know why the sample output is wrong for this problem. Unless I miss something from the below link:
https://uva.onlinejudge.org/index.php?o ... oblem=3562

The sample input is:

5 11
1 2 3 4 5

The sample output:

5

Should it be 3 instead of 5??

Kind Regards
Kazi
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 1121 - Subsequence

Post by uDebug »

Kazi_Tanvir_Ahsan wrote:I really need to know why the sample output is wrong for this problem. Unless I miss something from the below link:
https://uva.onlinejudge.org/index.php?o ... oblem=3562

The sample input is:

5 11
1 2 3 4 5

The sample output:

5

Should it be 3 instead of 5??

Kind Regards
Kazi
Yes, you're right. Thanks for sharing. It should be

Code: Select all

3
instead of

Code: Select all

5
If you're in doubt, please check
http://www.udebug.com/UVa/1121
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.
hquilo
New poster
Posts: 13
Joined: Fri May 02, 2014 9:45 pm

Re: 1121 - Subsequence

Post by hquilo »

Just in case: you need to output 0 in case there is no such a subsequence with sum at least s.
Post Reply

Return to “Volume 11 (1100-1199)”