Submission #128165

#	Time	Username	Problem	Language	Result	Execution time	Memory
128165		TadijaSebez	Lottery (CEOI18_lot)	C++11	100 / 100	777 ms	8492 KiB

lot

#include <bits/stdc++.h>
using namespace std;
const int N=10050;
const int K=105;
int dp[2][N],a[N],k[K],ans[K][N],cnt[N],n,l,q,m;
void Solve(int x, int t)
{
	for(int i=0;i<=l;i++) cnt[i]=0;
	for(int i=1;i<=m;i++) if(i!=x) cnt[dp[t][i]]++;
	for(int i=1;i<=l;i++) cnt[i]+=cnt[i-1];
	for(int i=1;i<=q;i++) ans[i][x]=cnt[k[i]];
}
int main()
{
	scanf("%i %i",&n,&l);
	for(int i=1;i<=n;i++) scanf("%i",&a[i]);
	scanf("%i",&q);
	for(int i=1;i<=q;i++) scanf("%i",&k[i]);
	m=n-l+1;
	for(int i=1;i<=m;i++) for(int j=0;j<l;j++) dp[0][i]+=a[1+j]!=a[i+j];
	Solve(1,0);
	int t=1;
	for(int i=2;i<=m;i++)
	{
		for(int j=1;j<=m;j++) dp[t][j]=0;
		for(int j=0;j<l;j++) dp[t][1]+=a[1+j]!=a[i+j];
		for(int j=2;j<=m;j++)
		{
			dp[t][j]=dp[t^1][j-1];
			dp[t][j]-=a[i-1]!=a[j-1];
			dp[t][j]+=a[i+l-1]!=a[j+l-1];
		}
		Solve(i,t);
		t^=1;
	}
	for(int i=1;i<=q;i++) for(int j=1;j<=m;j++) printf("%i%c",ans[i][j],j==m?'\n':' ');
	return 0;
}

Compilation message (stderr)

lot.cpp: In function 'int main()':
lot.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&l);
  ~~~~~^~~~~~~~~~~~~~~
lot.cpp:16:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i",&a[i]);
                        ~~~~~^~~~~~~~~~~~
lot.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&q);
  ~~~~~^~~~~~~~~
lot.cpp:18:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=q;i++) scanf("%i",&k[i]);
                        ~~~~~^~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20