Submission #71029

#	Time	Username	Problem	Language	Result	Execution time	Memory
71029		sebinkim	Lottery (CEOI18_lot)	C++14	100 / 100	645 ms	12608 KiB

lot

#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> pii;

int A[10101], T[10101], S[10101];
pii Q[111];
int ans[111][10101], print[111][10101];
int n, l, q;

int main()
{
	int i, j;
	
	scanf("%d%d", &n, &l);
	
	for(i=1; i<=n; i++){
		scanf("%d", A+i);
	}
	
	scanf("%d", &q);
	
	for(i=1; i<=q; i++){
		scanf("%d", &Q[i].first);
		Q[i].second = i;
	}
	
	sort(Q + 1, Q + q + 1);
	
	for(i=1; i<=q; i++){
		T[Q[i].first + 1] ++;
	}
	
	T[0] = 1;
	for(i=1; i<=n; i++){
		T[i] += T[i - 1];
	}
	
	for(i=1; i<n; i++){
		for(j=0; j<=i+1; j++) S[j] = 0;
		for(j=i; j>=1; j--){
			// (j, n - i + j)
			if(A[j] == A[n - i + j]){
				S[j] ++; S[max(j - l, 0)] --;
			}
			S[j] += S[j + 1];
			if(n - i + j <= n - l + 1) ans[T[l - S[j]]][j] ++;
			ans[T[l - S[j]]][n - i + j] ++;
		}
	}
	
	for(i=1; i<=q; i++){
		for(j=1; j<=n; j++){
			ans[i][j] += ans[i - 1][j];
			print[Q[i].second][j] = ans[i][j];
		}
	}
	
	for(i=1; i<=q; i++){
		for(j=1; j<=n-l+1; j++){
			printf("%d ", print[i][j]);
		}
		printf("\n");
	}
	
	return 0;
}

Compilation message (stderr)

lot.cpp: In function 'int main()':
lot.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &l);
  ~~~~~^~~~~~~~~~~~~~~~
lot.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", A+i);
   ~~~~~^~~~~~~~~~~
lot.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
lot.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &Q[i].first);
   ~~~~~^~~~~~~~~~~~~~~~~~~

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