## 1121 - Subsequence

Moderator: Board moderators

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

### 1121 - Subsequence

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

}

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

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

Use Sliding Window to get AC

Kazi_Tanvir_Ahsan
New poster
Posts: 1
Joined: Tue Oct 06, 2015 2:56 am

### 1121 - Subsequence

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

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``

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!

hquilo
New poster
Posts: 13
Joined: Fri May 02, 2014 9:45 pm

### Re: 1121 - Subsequence

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